Transcript All
Computer Networking
[email protected]
2007.9-11
Introduction
1-1
About Textbook
Computer Networking:A
Top Down Approach
Featuringthe Internet,
3rd edition.
Jim Kurose, Keith Ross
Addison-Wesley, July 2004.
高等教育出版社 (影印版)
Feature
Primer
Guide
English reading materials
Application Oriented
• Ethereal
• Programming
Top Down
Introduction
1-2
Reading list
COMPUTER NETWORKS,
FOURTH EDITION
Andrew S.Tanenbaum
Pearson Education &清华大学出版
社
Computer Networks, A Systems
Approach
Fourth Edition
Larry L.Peterson;Bruce S.Davie
Morgan Kaufmann & 机械工业出版
社
Introduction
1-3
Schedule
Introduction 3
应用层(Application Layer) 4
传输层 (Transport Layer) 4
网络层 (The Network Layer) 4
数据链路层(The Link Layer and Local
Area Networks) 3
无线网络(Wireless and Mobile Networks) 1
多媒体网络(Multimedia Networking)
网络安全 (Security in Computer Networks) 2
网络管理(Network Management)
Introduction
1-4
Introduction
Lecture 1: 1.1 -1.3
What is the Internet?
Circuit Switching(电路交换) and Packet
Switching(分组交换)
Lecture 2:1.4-1.6
Delay and Loss in Packet Switching
Physical Media(物理介质)
ISP and internet topology
Lecture 3: 1.7-1.8
Internet and ISO service models
History
Introduction
1-5
Application Layer
Lecture 4: 2.1-2.2
Principles of
Application Layer
Web and HTTP
Lecture 5: 2.3-2.6
FTP
Electronic Mail
P2P(点对点)
Lecture 6: 2.7-2.9
Socket Programming
• TCP(传输控制协议)
• UDP(用户数据包协议)
• SMTP, POP3, IMAP
DNS(域名系统)
Introduction
1-6
Transport Layer 4
Lecture 7: 3.1-3.3
Principles of Transport
Layer
Multiplexing and
Demultiplexing (多路复
用与解多路复用)
UDP
Lecture 9: 3.5
TCP
• Segment structure(报文结构)
• Reliable Data Transfer(可靠数
据传输)
• Flow control(流控制)
• Connection Management(连接
控制)
Lecture 8: 3.4
Lecture 10: 3.6-3.7
Principles of Reliable
Principles of Congestion
Data Transfer (可靠性
Control(拥塞控制原理)
数据传输原理)
TCP Congestion Control
Introduction
1-7
Network Layer 4
Lecture 11: 4.1-4.3
Introduction
Virtual circuit and
Datagram Network(虚电
路和数据报网络)
Router(路由器)
Lecture 12:4.4
IP: Internet Protocol
• Datagram Format(报文
格式)
• IPv4
• ICMP(internet Control
Message Protocol)
• IPv6
Lecture 13: 4.5
Routing Algorithms(路由算
法)
• Link state(链路状态)
• Distance Vector(距离向量)
• Hierarchical routing(层次
路由)
Lecture 14: 4.6-4.7
Routing in Internet
• RIP(路由信息协议)
• OSPF(开放最短路径)
• BGP(边界网关协议)
Multicast routing(多播路由
)
Introduction
1-8
Link Layer and Local Area Networks 3
Lecture 15: 5.1-5.3
Lecture 17: 5.6-5.8
Introduction
Hubs and Switches(交换机
Error-Detection and
)
Correction (差错检测和
PPP(点对点协议)
纠错技术)
Link Virtualization网络
Multiple Access
作为链路层)
Protocols(多路访问协议)
• ATM(异步传输模式网络)
Lecture 16: 5.4-5.5
Ling-Layer Addressing(
链路层编址)
Ethernet
• MPLS(多协议标签交换)
Introduction
1-9
Wireless networks 3
Lecture 18: 6.1-6.4
introduction
Wireless Links and Network
Characteristics(无线链路和网络特征)
802.11
Cellular Internet
Introduction
1-10
Network Security 2
Lecture 19 8.1-8.3
Introduction
Principles of Cryptography(密码学)
Authentication (鉴别)
Lecture 20 8.4-8.6
Integrity(完整性)
Key Distribution and Certification (密钥分发和
认证)
Firewall(防火墙)
Introduction
1-11
Chapter 1: Introduction
Our goal:
Overview:
get “feel” and
what’s the Internet
terminology(术语)
more depth, detail
later in course
approach:
use Internet as
example
Other:intranet
what’s a protocol?
network edge
network core
access net, physical media
Internet/ISP structure
performance: loss, delay
protocol layers, service models
network modeling
Introduction
1-12
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 (Internet
Service Providers)
1.6 Delay & loss in packet-switched networks
1.7 Protocol layers, service models
1.8 History
Introduction
1-13
What’s the Internet: “nuts and bolts”
view
Hardware and software
millions of connected
computing devices: hosts =
end systems
running network apps
communication links
Fiber(光纤), copper, radio,
router
server
workstation
mobile
local ISP
regional ISP
satellite
transmission rate =
bandwidth
routers: forward packets
(Internet Service Providers
(ISP)
Internet Content
Provider(ICP)
company
network
Introduction
1-14
What’s the Internet: “nuts and bolts” view
protocols control sending,
receiving of msgs
e.g., TCP, IP, HTTP, FTP, PPP
Internet: “network of
router
server
workstation
mobile
local ISP
networks”
loosely hierarchical
public Internet versus
private intranet
Internet standards
RFC: Request for comments
IETF: Internet Engineering
Task Force
regional ISP
company
network
Introduction
1-15
“Cool” internet appliances
IP picture frame
http://www.ceiva.com/
Internet phones
More applications?
World’s smallest web server
http://www-ccs.cs.umass.edu/~shri/iPic.html
Introduction
1-16
What’s the Internet: a service view
communication infrastructure
enables distributed
applications(分布式应用):
Web, email, games, ecommerce(电子商务), file
sharing
C/S,B/S,P2P
communication services
provided to apps:
Connectionless unreliable
connection-oriented reliable
Provide ?
BandWidth guarantee(保证)?
Dealy guarantee?
Introduction
1-17
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
Protocol and agent
http ,tcp , ed2k…
IE,cuteftp , emule
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-18
What’s a protocol?
a human protocol and a computer network protocol:
Hi
TCP connection
request
Hi
TCP connection
response
Got the
time?
Get http://www.awl.com/kurose-ross
2:00
<file>
time
Q: Protocol Vs Interface
Introduction
1-19
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-20
A closer look at network structure:
network edge:
applications
hosts
network core:
routers
network of networks
access networks,
physical media:
communication links
Introduction
1-21
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. Skype, BitTorrent agent,
KaZaA,ED2K agent
Introduction
1-22
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
Q:keep state anywhere?
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
Introduction
1-23
Network edge: connectionless service
App’s using TCP:
Goal: data transfer
between end systems
same as before!
UDP - User Datagram
Protocol [RFC 768]:
connectionless
unreliable data
transfer
no flow control
no congestion control
HTTP (Web), FTP (file
transfer), Telnet (remote
login), SMTP (email)
App’s using UDP:
streaming media,
teleconferencing, DNS,
Internet telephony
Q: connection-oriented
and connectionless run
over the other?
Introduction
1-24
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-25
The Network Core
mesh of interconnected
routers
how is data transferred
through net?
Reserved or not?
circuit switching(电路交换
): dedicated circuit per
call: telephone
net(changing)
packet-switching(分组交
换): data sent thru net in
discrete “chunks”
Introduction
1-26
Network Core: Circuit Switching
End-end resources
reserved for “call”
link bandwidth, switch
capacity
resources: no sharing
circuit-like (guaranteed)
performance
call setup required
Q:Connection-Oriented?
Introduction
1-27
Network Core: Circuit Switching
network resources
(e.g., bandwidth)
divided into “pieces”
pieces allocated to calls
resource piece idle if
dividing link bandwidth into
“pieces”
frequency division(频分)
time division(时分)
not used by owning call
(no sharing)
Q:Is adsl Circuit
Switching?
Introduction
1-28
Circuit Switching: FDM and TDM
Example:
FDM 频分
4 users
frequency
time
TDM
时分
frequency
time
Introduction
1-29
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?
All links are 1.536 Mbps
Each link uses TDM with 24 slots/sec
500 msec to establish end-to-end circuit
Bandwidth waste?
Let’s work it out!
Introduction
1-30
Network Core: Packet Switching
each end-end data stream
resource contention:
divided into packets
congestion(拥塞):
user A, B packets share
packets queue, wait for
network resources
link use
each packet uses full link
store and forward(存储
bandwidth
&转发): packets move
resources used as needed
one hop at a time
dest addr in Packet header
Node receives
Q:connectionless oriented?
complete packet
before forwarding
Bandwidth division into “pieces”
Dedicated allocation
Resource reservation
Introduction
1-31
Packet Switching: Statistical Multiplexing
100 Mb/s
Ethernet
A
B
statistical multiplexing
C
1.5 Mb/s
queue of packets
waiting for output
link
D
E
Sequence of A & B packets shared on demand
statistical multiplexing.(统计多路复用)
TDM: each host gets same slot.
Introduction
1-32
Packet-switching: store-and-forward
(存储转发)
L
R
Takes L/R seconds to
R
transmit (push out)
packet of L bits on to
link or R bps
Entire packet must
arrive at router before
it can be transmitted
on next link: store and
forward
delay = 3L/R (assuming
zero propagation delay)
R
Example:
L = 7.5 Mbits
R = 1.5 Mbps
delay = 15 sec
more on delay shortly …
Introduction
1-33
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
circuit-switching:
10 users
packet switching:
with 35 users,
probability > 10 active
less than .0004
N users
1 Mbps link
Q: how did we get value 0.0004?
Q: fair?
Q:PC2Phone? How does it work?
Introduction
1-34
Packet switching vs circuit switching
Is packet switching a 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 (chapter 7)
power network vs power host
P63 problem 2
TCP ,UDP, packet witching , circuit swithing , connectionoriented,connectionless-oriented
Introduction
1-35
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-36
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?
B/S ,b/S
shared or dedicated?
Introduction
1-37
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”
Integrated Services Digital
Network (ISDN)
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-38
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
Most without power supply
Introduction
1-39
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-40
Wireless access networks
shared wireless access
network connects end system
to router
via base station or “access point”
wireless LANs:
802.11b/g (WiFi): 11 or 54 Mbps
wider-area wireless access
provided by telco operator
3G ~ 384 kbps
• Will it happen??
• TD-CDMA in china
GPRS
router
base
station
mobile
hosts
Q:what type of wirless services in us?
Q: what is 2G 2.5G 3G ? 3.5G 4G?
Introduction
1-41
Home networks
Typical home network components:
ADSL(Asymmetric Digital Subscriber Line) or cable modem
Ethernet
Fiber , Twisted Pair
wireless access point
router/firewall/NAT
(Network address translation)
to/from
cable
headend
cable
modem
router/
firewall
Ethernet
wireless
laptops
wireless
access
point
Q:Desing a home network for your home or dormitory
Introduction
1-42
Physical Media
Bit: propagates between
transmitter/rcvr pairs
physical link: what lies
between transmitter &
receiver
guided media:
signals propagate in solid
media: copper, fiber, coax
unguided media:
signals propagate freely,
e.g., radio
Twisted Pair (TP)
two insulated copper
wires
Category 3: traditional
phone wires, 10 Mbps
Ethernet
• Less KM
Category 5:
100Mbps Ethernet
• UTP
• TIA/EIA 568A/B
• Less 100M
Introduction
1-43
Physical Media: coax, fiber
Coaxial cable:
Fiber optic cable(光纤):
conductors(同芯铜线)
Bidirectional(双向)
Baseband(基带):
pulses, each pulse a bit
high-speed operation:
two concentric copper
single channel on cable
legacy Ethernet
Broadband(宽带):
multiple channels on
cable
HFC
glass fiber carrying light
high-speed point-to-point
transmission (e.g., 10’s100’s Gps)
Up to 100KM
low error rate: repeaters
spaced far apart ; avoid
electromagnetic noise
Introduction
1-44
Physical media: radio
signal carried in
electromagnetic
spectrum(电磁波)
no physical “wire”
bidirectional
propagation
environment effects:
Reflection(反射)
obstruction by objects(
障碍物)
Interference(干涉)
Radio link types:
terrestrial microwave(陆地
微波)
e.g. up to 45 Mbps channels
LAN (e.g., Wifi)
11Mbps, 54 Mbps
wide-area (e.g., cellular)
e.g. 3G: hundreds of kbps
satellite
Kbps to 45Mbps channel (or
multiple smaller channels)
270 msec end-end delay
geosynchronous versus low
altitude
Introduction
1-45
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-46
Internet structure: network of networks
at center: “tier-1” ISPs (e.g., Cernet, Telcom,Unicome,
CNC), national/international coverage
treat each other as equals
Tier-1
providers
interconnect
(peer)
privately
Tier 1 ISP
Tier 1 ISP
NAP
Tier-1 providers
also interconnect
at public network
access points
(NAPs)
Tier 1 ISP
Introduction
1-47
Internet structure: network of networks
China backbone network
“Tier-2” ISPs: smaller (often regional) ISPs
Connect to one or more tier-1 ISPs, possibly other tier-2 ISPs
Cernet wuhan NOC , Telcom wuhan NOC
Tier-2 ISP pays
tier-1 ISP for
connectivity to
rest of Internet
tier-2 ISP is
customer of
tier-1 provider
Tier-2 ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
NAP
Tier 1 ISP
Tier-2 ISPs
also peer
privately with
each other,
interconnect
at NAP
Tier-2 ISP
Tier-2 ISP
Introduction
1-48
Internet structure: network of networks
“Tier-3” ISPs and local ISPs
last hop (“access”) network (closest to end systems)
Cernet CUG NOC , Wuhan Telcom
local
ISP
Local and tier3 ISPs are
customers of
higher tier
ISPs
connecting
them to rest
of Internet
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
Introduction
1-49
Cernet
Introduction
1-50
Internet structure: network of networks
a packet passes through many networks!
local
ISP
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
Introduction
1-51
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-52
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)
A
B
packets queueing (delay)
free (available) buffers: arriving packets
dropped (loss) if no free buffers
Introduction
1-53
Four sources of packet delay
1. processing(处理) Delay
check bit errors
determine output link
2. queueing(排队延时)
time waiting at output
link for transmission
depends on congestion
level of router
transmission
A
propagation
B
nodal
processing
queueing
Introduction
1-54
Delay in packet-switched networks
3. Transmission(传输)
delay:
R=link bandwidth (bps)
L=packet length (bits)
time to send bits into
link = L/R
transmission
A
4. Propagation(传播) delay:
d = length of physical link
s = propagation speed in
medium (~2x108 m/sec)
propagation delay = d/s
Note: s and R are very
different quantities!
propagation
B
nodal
processing
queueing
Introduction
1-55
Processing Delay
Make sure packet has not been corrupted
Forward to right output link queue
Schedule the next packet to be
transmitted from queue
Introduction
1-56
transmission time vs propagatedelay--Caravan analogy (旅行队类比)
100 km
ten-car
caravan
toll
booth
Cars “propagate” at
100 km/hr
Toll booth takes 12 sec to
service a car
(transmission time)
car~bit; caravan ~ packet
Q: How long until caravan
is lined up before 2nd toll
booth?
100 km
toll
booth
Time to “push” entire
caravan through toll
booth onto highway =
12*10 = 120 sec
Time for last car to
propagate from 1st to
2nd toll both:
100km/(100km/hr)= 1 hr
A: 62 minutes
Introduction
1-57
Caravan analogy (more)
100 km
ten-car
caravan
toll
booth
Cars now “propagate” at
1000 km/hr
Toll booth now takes 1
min to service a car
Q: Will cars arrive to
2nd booth before all
cars serviced at 1st
booth?
100 km
toll
booth
Yes! After 7 min, 1st car
at 2nd booth and 8th cars
still at 1st booth.
1st bit of packet can
arrive at 2nd router
before packet is fully
transmitted at 1st router!
Introduction
1-58
One packet, One Link
Packet Size: P bits
Bandwidth: R bps
Propagation delay: T sec
At what time is the sending buffer empty?
P/R : Packet Transmission Delay
And does the first bit get delivered B?:
T : Propagation Delay ? How get it?
does the last bit get delivered?:
T+P/R: Arrival time at B
Introduction
1-59
One packet, One Link
Packet Size: P bits
Bandwidth: R bps
Propagation delay: T sec
At what time is the sending buffer empty?
P/R : Packet Transmission Delay
does the first bit get delivered?:
T : Propagation Delay ? How get it?
does the last bit get delivered?:
T+P/R: Arrival time at B
Introduction
1-60
Timing Diagram
Introduction
1-61
Switching: Store and Forward
A packet is stored before being
forwarded (sent)
Introduction
1-62
Queueing
Packet Size: P bits
Bandwidth: R bps
Propagation delay: T sec
The queue has Q bits when packet arrives packet
has to wait for the queue to drain before being
transmitted
Introduction
1-63
Store and Forward: Multiple Packet Example
Introduction
1-64
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-65
Queueing delay
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!
How do solve it in Internet ?
Introduction
1-66
“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.
• TTL & ICMP
• Appliction Limited
3 probes
3 probes
3 probes
Introduction
1-67
“Real” Internet delays and routes
traceroute: www.cernet.edu.cn to 202.114.194.x
Three delay measurements from
1 202.112.6.17 (202.112.6.17) 1.115 ms 0.178 ms 0.164 ms
2 cd0.cernet.net (202.112.53.73) 0.688 ms 1.155 ms 0.659 ms
3 202.112.36.114 (202.112.36.114) 18.864 ms * 18.908 ms
4 gz1.cernet.net (202.112.53.78) 18.297 ms 18.270 ms 18.263 ms
5 * 218.199.142.226 (218.199.142.226) 18.565 ms 18.537 ms BeiJing-wuhan
6***
7***
* means no response (probe lost, router not replying)
8* **
Tracert www.cernet.edu.cn
Ping
www.cernet.edu.cn
no response
no response
Q: what make different delay time?
Introduction
1-68
Packet loss
queue preceding link in buffer has finite
capacity
when packet arrives to full queue, packet is
dropped lost packet may be retransmitted(
重传) by previous node, by source end
system, or not retransmitted at all
Introduction
1-69
Network performance metrics
Network-centric metrics
Reliability, queue lengths, load, etc
Network service providers try to provide best
possible service
End-user centric metrics
Throughput, packet loss, delay etc
Users concerned about the performance of
specific applications
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
Protocol “Layers”
Networks are complex!
many “pieces”:
hosts
routers
links of various
media
applications
protocols
hardware,
software
How to program a complex
system?
Layers: each layer implements
a service
via its own internal-layer
actions
relying on services
provided by layer below
Introduction
1-72
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-73
Protocol Hierarchies
Layers, protocols, and interfaces.
Introduction
1-74
Internet protocol stack
application: supporting network
applications
FTP, SMTP, HTTP
transport: process-process data
transfer
TCP, UDP
network: routing of datagrams from
source to destination
IP, routing protocols
link: data transfer between
application
transport
network
link
physical
neighboring network elements
PPP, Ethernet
physical: bits “on the wire”
Introduction
1-75
Encapsulation
source
message
segment
M
Ht
M
datagram Hn Ht
M
frame Hl Hn Ht
M
application
transport
network
link
physical
link
physical
switch
destination
M
Ht
M
Hn Ht
Hl Hn Ht
M
M
application
transport
network
link
physical
Hn Ht
Hl Hn Ht
M
M
network
link
physical
Hn Ht
M
router
Introduction
1-76
Reference Models
The OSI
reference
model.
Introduction
1-77
Reference Models (2)
The TCP/IP reference model.
Introduction
1-78
Reference Models (3)
Protocols and networks in the TCP/IP
model initially.
Introduction
1-79
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-80
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 public demonstration
NCP (Network Control Protocol)
first host-host protocol
first e-mail program
ARPAnet has 15 nodes
Introduction
1-81
Internet History
1972-1980: Internetworking, new and proprietary nets
1970: ALOHAnet satellite
network in Hawaii
1974: Cerf and Kahn architecture for
interconnecting networks
1976: Ethernet at Xerox
PARC
ate70’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-82
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-83
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, P2P file sharing
network security to
forefront
est. 50 million host, 100
million+ users
backbone links running at
Gbps
1994 Cernet
1996 Chinanet
Introduction
1-84
ATM: Asynchronous Transfer Mode nets
Internet:
today’s de facto
standard for global
data networking
1980’s:
telco’s develop ATM:
competing network
standard for carrying
high-speed voice/data
standards bodies:
ATM Forum
ITU
ATM principles:
small (48 byte payload, 5
byte header) fixed length
cells (like packets)
fast switching
small size good for voice
virtual-circuit network:
switches maintain state for
each “call”
well-defined interface
between “network” and
“user” (think of telephone
company)
Introduction
1-85
ATM layers
ATM Adaptation
Layer (AAL):
interface to upper
layers
end-system
segmentation/rea
ssembly
ATM Layer: cell
switching
Physical
application
TCP/UDP
IP
AAL
ATM
physical
application
TCP/UDP
IP
AAL
ATM
physical
Where’s the application?
ATM: lower layer
functionality only
IP-over ATM: later
ATM
physical
application
TCP/UDP
IP
AAL
ATM
physical
application
TCP/UDP
IP
AAL
ATM
physical
Introduction
1-86
Introduction: Summary
Covered a “ton” of material!
Internet overview
what’s a protocol?
network edge, core, access
network
packet-switching versus
circuit-switching
Internet/ISP structure
performance: loss, delay
layering and service
models
history
You now have:
context, overview,
“feel” of networking
more depth, detail to
follow!
Introduction
1-87
Be a protocol detective…
Download a packet sniffer,
A packet sniffer allows you to examine the
packets sent from and received at your
host.
Classified by protocol.
This allows you to see how your host is
communicating with other devices of the
internet
Introduction
1-88
Ethereal Lab
Packet sniffer software
Winpcap
• The Windows Packet Capture Library
Ethereal
• www.ethereal.com
• GTK2
• svn checkout
http://anonsvn.ethereal.com/ethereal/trunk ethereal
URLSnooper2
Nat Sniffer pro
Introduction
1-89
Ethereal Lab
Introduction
1-90
Ethereal Lab
Start capture
Capture ->Interface
Capture ->start
Capture ->restart
Capture ->stop
Capture -> Capture filter
Introduction
1-91
Ethereal Lab
List the different protocols that appear in the protocol
column in the unfiltered packet-listing window
How long did it take from when the HTTP GET message
was sent until the HTTP OK reply was received?
What is the Internet address of the www.cug.edu.cn?
What is the Internet address of your computer?
Display only the packets sent by your host.
What is the MAC address of your host? Display only the
packets received by your host. Do this by filtering MAC
addresses.
Display only the packets that have been received by your
host. Do this by filtering IP addresses.
Display only the HTTP packets that have been sent by your
host
Introduction
1-92
Homework
Problems
5 6 14 16
Introduction
1-93
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Have fun!
Introduction
1-94
Chapter 2: Application Layer
Our goals:
conceptual,
implementation
aspects of network
application protocols
transport-layer
service models
client-server
paradigm
peer-to-peer
learn about protocols
by examining popular
application-level
protocols
HTTP
FTP
SMTP / POP3 / IMAP
DNS
programming network
applications
socket API
Introduction
1-95
Some network apps
E-mail
Internet telephony
Web
Real-time video
Instant messaging
Remote login
P2P file sharing
Multi-user network
games
Streaming stored
video clips
conference
Massive parallel
computing
Introduction
1-96
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-97
Creating a network app
Write programs that
run on different end
systems and
communicate over a
network.
e.g., Web: Web server
software communicates
with browser software
little software written for
devices in network core
network core devices do
not run user application
code
application on end systems
allows for rapid app
development, propagation
application
transport
network
data link
physical
application
transport
network
data link
physical
application
transport
network
data link
physical
Introduction
1-98
Application architectures
Client-server
B/S
Peer-to-peer (P2P)
Hybrid(混合) of client-server and P2P
Introduction
1-99
Client-server architecture
server:
always-on host
permanent IP address
server farms for scaling
clients:
communicate with
server
may be intermittently
connected
may have dynamic IP
addresses
do not communicate
directly with each other
Introduction
1-100
Pure P2P architecture
P2P(peer-to-peer)
no always-on server
arbitrary end systems
directly communicate
peers are intermittently
connected and change IP
addresses
example: Gnutella
Gnutella 2
Q: more Network workload?
Highly scalable but difficult to
manage
Introduction
1-101
Hybrid of client-server and P2P
Skype
Internet telephony app
Finding address of remote party: centralized server(s)
Client-client connection is direct (not through server)
Instant messaging
Chatting between two users is P2P
Presence detection/location centralized:
• User registers its IP address with central server when it
comes online
• User contacts central server to find IP addresses of
buddies
Introduction
1-102
Processes communicating
Process: program running within
a host.
within same host, two
processes communicate using
inter-process communication
(defined by OS).
processes in different hosts
communicate by exchanging
messages
Processes running in
different hosts communicate
with an application-layer
protocol
Client process: process that
initiates communication
Server process: process that
waits to be contacted
Note: applications with
P2P architectures have
client processes &
server processes
Introduction
1-103
Sockets
process sends/receives
messages to/from its
socket
socket
sending process push
message
sending process relies on
transport infrastructure
on other side of door which
brings message to socket
at receiving process
host or
server
host or
server
process
controlled by
app developer
process
socket
socket
TCP with
buffers,
variables
Internet
TCP with
buffers,
variables
controlled
by OS
API: (1) choice of transport protocol; (2) ability to fix
a few parameters (lots more on this later)
Introduction
1-104
Addressing processes
API: application
programming interface
defines interface
between application
and transport layer
socket: Internet API
two processes
communicate by sending
data into socket,
reading data out of
socket
to receive messages,
process must have
identifier
host device has
unique32-bit IP
address
Q: does IP address of
host on which process
runs suffice for
identifying the
process?
Introduction
1-105
Addressing processes
Answer: NO, many
processes can be
running on same host
identifier includes both
IP address and port
numbers associated
with process on host.
Example port numbers:
HTTP server: 80
Mail server: 25
to send HTTP message
to gaia.cs.umass.edu web
server:
IP address: 128.119.245.12
Port number: 80
Nat
Introduction
1-106
App-layer protocol defines
Types of messages
exchanged,
e.g., request, response
Message syntax:
what fields in messages &
how fields are delineated
Message semantics
meaning of information in
fields
Rules for when and how
Public-domain protocols:
defined in RFCs
http://www.ietf.org/rfc
.html
allows for
interoperability
e.g., HTTP, SMTP
Proprietary protocols:
e.g., KaZaA
processes send &
respond to messages
Introduction
1-107
Where do Application Protocols Run?
Introduction
1-108
What transport service does an app need?
Data loss
some apps (e.g., audio) can
tolerate some loss
other apps (e.g., file
transfer, telnet) require
100% reliable data
transfer
Timing
some apps (e.g.,
Internet telephony,
interactive games)
require low delay to be
“effective”
Bandwidth
some apps (e.g.,
multimedia) require
minimum amount of
bandwidth to be
“effective”
other apps (“elastic
apps”) make use of
whatever bandwidth
they get
Introduction
1-109
Transport service requirements of common apps
Data loss
Bandwidth
Time Sensitive
file transfer
e-mail
Web documents
real-time audio/video
no loss
no loss
no loss
loss-tolerant
no
no
no
yes, 100’s msec
stored audio/video
interactive games
instant messaging
loss-tolerant
loss-tolerant
no loss
elastic
elastic
elastic
audio: 5kbps-1Mbps
video:10kbps-5Mbps
same as above
few kbps up
elastic
Application
yes, few secs
yes, 100’s msec
yes and no
Introduction
1-110
Internet transport protocols services
TCP service:
connection-oriented: setup
required between client and
server processes
reliable transport between
sending and receiving process
flow control: sender won’t
overwhelm receiver
congestion control: throttle
sender when network
overloaded
does not provide: timing,
minimum bandwidth
guarantees
UDP service:
unreliable data transfer
between sending and
receiving process
does not provide:
connection setup,
reliability, flow control,
congestion control, timing,
or bandwidth guarantee
Q: Why is there a UDP?
Introduction
1-111
Internet apps: application, transport protocols
Application
e-mail
remote terminal access
Web
file transfer
streaming multimedia
Internet telephony
Application
layer protocol
Underlying
transport protocol
SMTP [RFC 2821]
Telnet [RFC 854]
HTTP [RFC 2616]
FTP [RFC 959]
proprietary
(e.g. RealNetworks)
proprietary
(e.g., Vonage,Dialpad)
TCP
TCP
TCP
TCP
TCP or UDP
typically UDP
Introduction
1-112
Chapter 2: Application layer
2.1 Principles of
network applications
app architectures
app requirements
2.2 Web and HTTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-113
Web and HTTP
First some jargon
Web page consists of objects
Object can be HTML (HyperText Markup Language)
file, JPEG image, Java applet, audio file,…
Web page consists of base HTML file which
includes several referenced objects
Each object is addressable by a URL (Uniform
Resource Locators)
Example URL:
www.someschool.edu/someDept/pic.gif
host name
path name
Introduction
1-114
Web object example:
<IMG height=50 src="cnnic.jpg">
<OBJECT codeBase="plugin/PowerPlr.ocx#"
type="application/x-oleobject"
classid="clsid:2354A44B-3CEB-4829-9940545B03103538" >
<a href="LectureNotes/tse_final_review.pdf">
tse_final_review.pdf</a>
<script language=javascript> ….</script>
Aspx…
<asp:Login ID="Login1" runat="server">
</asp:Login>
Introduction
1-115
HTTP overview
HTTP: hypertext
transfer protocol
Web’s application layer
protocol
client/server model
client: browser that
requests, receives,
“displays” Web objects
server: Web server
sends objects in
response to requests
HTTP 1.0: RFC 1945
HTTP 1.1: RFC 2068
PC running
Explorer
Server
running
Apache Web
server
Mac running
Navigator
Introduction
1-116
HTTP overview (continued)
Uses TCP:
client initiates TCP
connection (creates socket)
to server, port 80
server accepts TCP
connection from client
HTTP messages (applicationlayer protocol messages)
exchanged between browser
(HTTP client) and Web
server (HTTP server)
TCP connection closed
HTTP is “stateless”
server maintains no
information about
past client requests
aside
Protocols that maintain
“state” are complex!
past history (state) must
be maintained
if server/client crashes,
their views of “state” may
be inconsistent, must be
reconciled
Introduction
1-117
HTTP connections
Nonpersistent HTTP
At most one object is
sent over a TCP
connection.
HTTP/1.0 uses
nonpersistent HTTP
Persistent HTTP
Multiple objects can
be sent over single
TCP connection
between client and
server.
HTTP/1.1 uses
persistent connections
in default mode
Introduction
1-118
Nonpersistent HTTP
(contains text,
Suppose user enters URL
references to 10
www.someSchool.edu/someDepartment/home.index
jpeg images)
1a. HTTP client initiates TCP
connection to HTTP server
(process) at
www.someSchool.edu on port 80
2. HTTP client sends HTTP
request message (containing
URL) into TCP connection
socket. Message indicates
that client wants object
someDepartment/home.index
1b. HTTP server at host
www.someSchool.edu waiting
for TCP connection at port 80.
“accepts” connection, notifying
client
3. HTTP server receives request
message, forms response
message containing requested
object, and sends message
into its socket
time
Introduction
1-119
Nonpersistent HTTP (cont.)
4. HTTP server closes TCP
5. HTTP client receives response
connection.
message containing html file,
displays html. Parsing html
file, finds 10 referenced jpeg
objects
time 6. Steps 1-5 repeated for each
of 10 jpeg objects
Introduction
1-120
Non-Persistent HTTP: Response time
Definition of RTT (Roundtrip time): time to send
a small packet to travel
from client to server
and back.
Response time:
one RTT to initiate TCP
connection
one RTT for HTTP
request and first few
bytes of HTTP response
to return
file transmission time
total = 2RTT+transmit time
initiate TCP
connection
RTT
request
file
time to
transmit
file
RTT
file
received
time
time
Introduction
1-121
Persistent HTTP
Nonpersistent HTTP issues:
requires 2 RTTs per object
OS overhead for each TCP
connection
browsers often open parallel
TCP connections to fetch
referenced objects
Persistent HTTP
server leaves connection
open after sending response
subsequent HTTP messages
between same client/server
sent over open connection
Persistent without pipelining:
client issues new request
only when previous
response has been received
one RTT for each
referenced object
Persistent with pipelining:
default in HTTP/1.1
client sends requests as
soon as it encounters a
referenced object
as little as one RTT for all
the referenced objects
Introduction
1-122
HTTP request message
two types of HTTP messages: request, response
HTTP request message:
ASCII (human-readable format)
request line
(GET, POST,
HEAD commands)
GET /somedir/page.html HTTP/1.1
Host: www.someschool.edu
User-agent: Mozilla/4.0
header Connection: close
lines Accept-language:fr
Carriage return,
line feed
indicates end
of message
(extra carriage return, line feed)
Introduction
1-123
HTTP request message: general format
Introduction
1-124
Uploading form input
Post method:
Web page often
includes form input
Input is uploaded to
server in entity body
URL method:
Uses GET method
Input is uploaded in
URL field of request
line:
www.somesite.com/animalsearch?monkeys&banana
Introduction
1-125
Method types
HTTP/1.0
GET
POST
HEAD
asks server to leave
requested object out of
response
HTTP/1.1
GET, POST, HEAD
PUT
uploads file in entity
body to path specified
in URL field
DELETE
deletes file specified in
the URL field
Introduction
1-126
HTTP response message
status line
(protocol
status code
status phrase)
header
lines
data, e.g.,
requested
HTML file
HTTP/1.1 200 OK
Connection close
Date: Thu, 06 Aug 1998 12:00:15 GMT
Server: Apache/1.3.0 (Unix)
Last-Modified: Mon, 22 Jun 1998 …...
Content-Length: 6821
Content-Type: text/html
data data data data data ...
Introduction
1-127
HTTP response status codes
In first line in server->client response message.
A few sample codes:
200 OK
request succeeded, requested object later in this message
301 Moved Permanently
requested object moved, new location specified later in
this message (Location:)
400 Bad Request
request message not understood by server
404 Not Found
requested document not found on this server
505 HTTP Version Not Supported
Introduction
1-128
Trying out HTTP (client side) for yourself
1. Telnet to your favorite Web server:
telnet cis.poly.edu 80
Opens TCP connection to port 80
(default HTTP server port) at cis.poly.edu.
Anything typed in sent
to port 80 at cis.poly.edu
2. Type in a GET HTTP request:
GET /~ross/ HTTP/1.1
Host: cis.poly.edu
By typing this in (hit carriage
return twice), you send
this minimal (but complete)
GET request to HTTP server
3. Look at response message sent by HTTP server!
Introduction
1-129
Let’s look at HTTP in action
telnet example
Homework
Ethereal example
Homework
How to identify different agent in server process?
Introduction
1-130
User-server state: cookies
Many major Web sites
use cookies
Four components:
1) cookie header line of
HTTP response message
2) cookie header line in
HTTP request message
3) cookie file kept on
user’s host, managed by
user’s browser
4) back-end database at
Web site
Example:
Susan access Internet
always from same PC
She visits a specific ecommerce site for first
time
When initial HTTP
requests arrives at site,
site creates a unique ID
and creates an entry in
backend database for
ID
Introduction
1-131
Cookies: keeping “state” (cont.)
client
Cookie file
server
usual http request msg
usual http response +
ebay: 8734
Cookie file
amazon: 1678
ebay: 8734
Set-cookie: 1678
usual http request msg
cookie: 1678
usual http response msg
one week later:
Cookie file
amazon: 1678
ebay: 8734
usual http request msg
cookie: 1678
usual http response msg
server
creates ID
1678 for user
cookiespecific
action
cookiespectific
action
Introduction
1-132
Cookies (continued)
What cookies can bring:
authorization
shopping carts
recommendations
user session state (Web e-
mail)
aside
Cookies and privacy:
cookies permit sites to
learn a lot about you
Who has 1679?
Infringement on
privacy?
How to keep “state”:
Protocol endpoints:
maintain state at
sender/receiver over
multiple transactions
cookies: http messages
carry state
Introduction
1-133
Web caches (proxy server)
Goal: satisfy client request without involving origin server
user sets browser: Web
accesses via cache
browser sends all HTTP
requests to cache
object in cache: cache
returns object
else cache requests
object from origin
server, then returns
object to client
origin
server
client
client
Proxy
server
origin
server
Introduction
1-134
More about Web caching
Cache acts as both
client and server
Typically cache is
installed by ISP
(university, company,
residential ISP)
Can it cache DHTM?
Why Web caching?
Reduce response time for
client request.
Reduce traffic on an
institution’s access link.
Internet dense with
caches: enables “poor”
content providers to
effectively deliver content
(but so does P2P file
sharing)
Introduction
1-135
Caching example
Assumptions
average object size = 100,000
bits
avg. request rate from
institution’s browsers to origin
servers = 15/sec
delay from institutional router
to any origin server and back
to router = 2 sec
Consequences
origin
servers
public
Internet
1.5 Mbps
access link
institutional
network
10 Mbps LAN
utilization on LAN = 15%
utilization on access link = 100%
total delay
= Internet delay +
access delay + LAN delay
= 2 sec + minutes + milliseconds
institutional
cache
Introduction
1-136
Caching example (cont)
Possible solution
increase bandwidth of access
link to, say, 10 Mbps
Consequences
origin
servers
public
Internet
utilization on LAN = 15%
utilization on access link = 15%
= Internet delay +
access delay + LAN delay
= 2 sec + msecs + msecs
often a costly upgrade
10 Mbps
access link
Total delay
institutional
network
10 Mbps LAN
institutional
cache
Introduction
1-137
Caching example (cont)
origin
servers
Install cache
suppose hit rate is .4
Consequence
public
Internet
40% requests will be
satisfied almost immediately
60% requests satisfied by
origin server
utilization of access link
reduced to 60%, resulting in
negligible delays (say 10
msec)
total avg delay = Internet
delay + access delay + LAN
delay = .6*(2.01) secs +
.4*milliseconds < 1.4 secs
P2P file sharing vs caching?
1.5 Mbps
access link
institutional
network
10 Mbps LAN
institutional
cache
Introduction
1-138
Conditional GET
Goal: don’t send object if
cache has up-to-date cached
version
cache: specify date of
cached copy in HTTP request
If-modified-since:
<date>
server: response contains no
object if cached copy is upto-date:
HTTP/1.0 304 Not
Modified
server
cache
HTTP request msg
If-modified-since:
<date>
HTTP response
object
not
modified
HTTP/1.0
304 Not Modified
HTTP request msg
If-modified-since:
<date>
HTTP response
object
modified
HTTP/1.0 200 OK
<data>
Introduction
1-139
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-140
FTP: the file transfer protocol
user
at host
FTP
FTP
user
client
interface
file transfer
local file
system
FTP
server
remote file
system
transfer file to/from remote host
client/server model
client: side that initiates transfer (either to/from
remote)
server: remote host
ftp: RFC 959
ftp server: port 21
Introduction
1-141
FTP: separate control, data connections
TCP control connection
port 21
FTP client contacts FTP
server at port 21, specifying
TCP as transport protocol
Client obtains authorization
over control connection
Client browses remote
directory by sending
commands over control
connection.
When server receives file
transfer command, server
opens 2nd TCP connection (for
file) to client (port,pasv)
After transferring one file,
server closes data
connection.
FTP
client
TCP data connection
port 20
FTP
server
Server opens another TCP
data connection to transfer
another file.
Control connection: “out of
band”
FTP server maintains “state”:
current directory, earlier
authentication
Introduction
1-142
FTP commands, responses
Sample commands:
sent as ASCII text over
control channel
USER username
PASS password
LIST return list of file in
Sample return codes
status code and phrase (as
current directory
RETR filename retrieves
STOR filename stores
(gets) file
(puts) file onto remote
host
Example :FTP anonymous
in HTTP)
331 Username OK,
password required
125 data connection
already open;
transfer starting
425 Can’t open data
connection
452 Error writing
file
Introduction
1-143
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-144
Electronic Mail
outgoing
message queue
user mailbox
user
agent
Three major components:
user agents
mail servers
mail
server
SMTP
simple mail transfer
protocol: SMTP
User Agent
“mail reader”
composing, editing, reading
mail messages
e.g. Outlook, foxmail,
Netscape Messenger
outgoing, incoming messages
stored on server
SMTP
mail
server
user
agent
SMTP
user
agent
mail
server
user
agent
user
agent
user
agent
Introduction
1-145
Electronic Mail: mail servers
user
agent
Mail Servers
mailbox contains incoming
messages for user(logic)
message queue of outgoing
(to be sent) mail messages
Mail delay,loss
SMTP protocol between mail
servers to send email
messages
client: sending mail
server
“server”: receiving mail
server
mail
server
SMTP
SMTP
mail
server
user
agent
SMTP
user
agent
mail
server
user
agent
user
agent
user
agent
Introduction
1-146
Electronic Mail: SMTP [RFC 2821]
uses TCP to reliably transfer email message from client
to server, port 25
direct transfer: sending server to receiving server
express
three phases of transfer
handshaking (greeting)
transfer of messages
closure
command/response interaction
commands: ASCII text
response: status code and phrase
messages must be in 7-bit ASCII
Introduction
1-147
Scenario: Alice sends message to Bob
1) Alice uses UA to compose
message and “to”
[email protected]
2) Alice’s UA sends message
to her mail server; message
placed in message queue
3) Client side of SMTP opens
TCP connection with Bob’s
mail server
1
user
agent
2
mail
server
3
4) SMTP client sends Alice’s
message over the TCP
connection
5) Bob’s mail server places the
message in Bob’s mailbox
6) Bob invokes his user agent
to read message
mail
server
4
5
6
user
agent
Introduction
1-148
Sample SMTP interaction
S:
C:
S:
C:
S:
C:
S:
C:
S:
C:
C:
C:
S:
C:
S:
220 hamburger.edu
HELO crepes.fr
250 Hello crepes.fr, pleased to meet you
MAIL FROM: <[email protected]>
250 [email protected]... Sender ok
RCPT TO: <[email protected]>
250 [email protected] ... Recipient ok
DATA
354 Enter mail, end with "." on a line by itself
Do you like ketchup?
How about pickles?
.
250 Message accepted for delivery
QUIT
221 hamburger.edu closing connection
Introduction
1-149
Try SMTP interaction for yourself:
telnet servername 25
see 220 reply from server
enter HELO, MAIL FROM, RCPT TO, DATA, QUIT
commands
above lets you send email without using email client
(reader)
Ethereal
Why can’t ban spam email?
Introduction
1-150
SMTP: final words
SMTP uses persistent
connections
SMTP requires message
(header & body) to be in 7bit ASCII
SMTP server uses
CRLF.CRLF to determine
end of message
Q:Web Mail?
Q:How to develope a mail
server?
Comparison with HTTP:
HTTP: pull
SMTP: push
both have ASCII
command/response
interaction, status codes
HTTP: each object
encapsulated in its own
response msg
SMTP: multiple objects
sent in multipart msg
Introduction
1-151
Mail message format
SMTP: protocol for
exchanging email msgs
RFC 822: standard for text
message format:
header lines, e.g.,
To:
From:
Subject:
different from SMTP
commands!
header
blank
line
body
body
the “message”, ASCII
characters only
Introduction
1-152
Message format: multimedia extensions
MIME: multimedia mail extension, RFC 2045, 2056
additional lines in msg header declare MIME content
type
MIME version
method used
to encode data
multimedia data
type, subtype,
parameter declaration
encoded data
From: [email protected]
To: [email protected]
Subject: Picture of yummy crepe.
MIME-Version: 1.0
Content-Transfer-Encoding: base64
Content-Type: image/jpeg
base64 encoded data .....
.........................
......base64 encoded data
Introduction
1-153
With foxmail
Introduction
1-154
Mail access protocols
user
agent
SMTP
SMTP
sender’s mail
server
access
protocol
user
agent
receiver’s mail
server
SMTP: delivery/storage to receiver’s server
Mail access protocol: retrieval from server
POP: Post Office Protocol [RFC 1939]
• authorization (agent <-->server) and download
IMAP: Internet Mail Access Protocol [RFC 1730]
• more features (more complex)
• manipulation of stored msgs on server
HTTP: Hotmail , Yahoo! Mail, etc.
Introduction
1-155
POP3 protocol
authorization phase
client commands:
user: declare username
pass: password
server responses
+OK
-ERR
transaction phase, client:
list: list message numbers
retr: retrieve message by
number
dele: delete
quit
S:
C:
S:
C:
S:
+OK POP3 server ready
user bob
+OK
pass hungry
+OK user successfully logged
C:
S:
S:
S:
C:
S:
S:
C:
C:
S:
S:
C:
C:
S:
list
1 498
2 912
.
retr 1
<message 1 contents>
.
dele 1
retr 2
<message 1 contents>
.
dele 2
quit
+OK POP3 server signing off
Introduction
on
1-156
POP3 (more) and IMAP
More about POP3
Previous example uses
“download and delete”
mode.
Bob cannot re-read email if he changes
client
“Download-and-keep”:
copies of messages on
different clients
POP3 is stateless
across sessions
IMAP
Keep all messages in
one place: the server
Allows user to
organize messages in
folders
IMAP keeps user state
across sessions:
names of folders and
mappings between
message IDs and folder
name
Introduction
1-157
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-158
DNS: Domain Name System
People: many identifiers:
SSN, name, passport #
Internet hosts, routers:
IP address (32 bit) used for addressing
datagrams
“name”, e.g.,
ww.yahoo.com - used by
humans
Q: map between IP
addresses and name ?
Domain Name System:
distributed database
implemented in hierarchy of
many name servers
application-layer protocol
host, routers, name servers to
communicate to resolve names
(address/name translation)
note: core Internet
function, implemented as
application-layer protocol
complexity at network’s
“edge”
Introduction
1-159
DNS
DNS services
Hostname to IP
address translation
Host aliasing
Canonical and alias
names
Mail server aliasing
Load distribution
Replicated Web
servers: set of IP
addresses for one
canonical name
Why not centralize DNS?
single point of failure
traffic volume
distant centralized
database
maintenance
doesn’t scale!
Introduction
1-160
Distributed, Hierarchical Database
Root DNS Servers
com DNS servers
yahoo.com
amazon.com
DNS servers DNS servers
org DNS servers
pbs.org
DNS servers
edu DNS servers
poly.edu
umass.edu
DNS serversDNS servers
Client wants IP for www.amazon.com; 1st approx:
Client queries a root server to find com DNS
server
Client queries com DNS server to get amazon.com
DNS server
Client queries amazon.com DNS server to get IP
address for www.amazon.com
Introduction
1-161
DNS: Root name servers
contacted by local name server that can not resolve name
root name server:
contacts authoritative name server if name mapping not known
gets mapping
returns mapping to local name server
a Verisign, Dulles, VA
c Cogent, Herndon, VA (also Los Angeles)
d U Maryland College Park, MD
k RIPE London (also Amsterdam,
g US DoD Vienna, VA
Frankfurt)
i Autonomica, Stockholm (plus 3
h ARL Aberdeen, MD
j Verisign, ( 11 locations)
other locations)
m WIDE Tokyo
e NASA Mt View, CA
f Internet Software C. Palo Alto,
CA (and 17 other locations)
13 root name
servers worldwide
b USC-ISI Marina del Rey, CA
l ICANN Los Angeles, CA
Introduction
1-162
TLD and Authoritative Servers
Top-level domain (TLD) servers: responsible
for com, org, net, edu, etc, and all top-level
country domains uk, fr, ca, jp.
Network solutions maintains servers for com TLD
Educause for edu TLD
Authoritative DNS servers: organization’s
DNS servers, providing authoritative
hostname to IP mappings for organization’s
servers (e.g., Web and mail).
Can be maintained by organization or service
provider
Introduction
1-163
Local Name Server
Does not strictly belong to hierarchy
Each ISP (residential ISP, company,
university) has one.
Also called “default name server”
When a host makes a DNS query, query is
sent to its local DNS server
Acts as a proxy, forwards query into hierarchy.
Introduction
1-164
Recursive queries
Host at cis.poly.edu
2
wants IP address for
gaia.cs.umass.edu
recursive query:
puts burden of name
root DNS server
3
7
6
TLD DNS server
local DNS server
resolution on contacted
name server
heavy load?
dns.poly.edu
1
5
4
8
requesting host
authoritative DNS server
dns.cs.umass.edu
cis.poly.edu
gaia.cs.umass.edu
Introduction
1-165
iterated query
root DNS server
iterated query:
2
contacted server replies
with name of server to
contact
“I don’t know this name,
but ask this server”
recursive query:
Host to the local DSN
Server
3
TLD DNS server
4
5
local DNS server
dns.poly.edu
1
8
requesting host
7
6
authoritative DNS server
dns.cs.umass.edu
cis.poly.edu
gaia.cs.umass.edu
Introduction
1-166
DNS: caching and updating records
once (any) name server learns mapping, it caches
mapping
cache entries timeout (disappear) after some
time
TLD servers typically cached in local name
servers
• Thus root name servers not often visited
update/notify mechanisms under design by IETF
RFC 2136
http://www.ietf.org/html.charters/dnsind-charter.html
Introduction
1-167
DNS records
DNS: distributed db storing resource records (RR)
RR format: (name,
Type=A
name is hostname
value is IP address
Type=NS
name is domain (e.g.
foo.com)
value is hostname of
authoritative name
server for this domain
value, type, ttl)
Type=CNAME
name is alias name for some
“canonical” (the real) name
www.ibm.com is really
servereast.backup2.ibm.com
value is canonical name
Type=MX
value is name of mailserver
associated with name
Introduction
1-168
DNS protocol, messages
DNS protocol : query and reply messages, both with
same message format
msg header
identification: 16 bit #
for query, reply to query
uses same #
flags:
query or reply
recursion desired
recursion available
reply is authoritative
Introduction
1-169
DNS protocol, messages
Name, type fields
for a query
RRs in response
to query
records for
authoritative servers
additional “helpful”
info that may be used
Introduction
1-170
Inserting records into DNS
Example: just created startup “Network Utopia”
Register name networkuptopia.com at a registrar (e.g., Network
Solutions)
Need to provide registrar with names and IP addresses of your
authoritative name server (primary and secondary)
Registrar inserts two RRs into the com TLD server:
(networkutopia.com, dns1.networkutopia.com, NS)
(dns1.networkutopia.com, 212.212.212.1, A)
Put in authoritative server Type A record for
www.networkuptopia.com and Type MX record for
networkutopia.com
How do people get the IP address of your Web site?
How do DDNS?
Introduction
1-171
Nslookup
Nslookup www.cug.edu.cn:
202.114.200.254
• 202.114.200.245
202.103.24.68
• 58.48.110.152
Introduction
1-172
DNS Summary
DNS is a crucial part of the internet
Namespace is hierarchical
Administration is distributed
It is vulnerable in various ways but no
more than other parts of the internet
infrastructure
Its performance is enhanced by caching
Dns “Hacks”?
Introduction
1-173
Chapter 2: Application layer
2.1 Principles of
network applications
app architectures
app requirements
2.2 Web and HTTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-174
P2P file sharing
Example
Alice runs P2P client
application on her
notebook computer
Intermittently
connects to Internet;
gets new IP address
for each connection
Asks for “Hey Jude”
Application displays
other peers that have
copy of Hey Jude.
Alice chooses one of
the peers, Bob.
File is copied from
Bob’s PC to Alice’s
notebook: HTTP
While Alice downloads,
other users uploading
from Alice.
Alice’s peer is both a
Web client and a
transient Web server.
All peers are servers =
highly scalable!
Introduction
1-175
P2P: centralized directory
original “Napster” design
1) when peer connects, it
informs central server:
Bob
centralized
directory server
1
peers
IP address
content
2) Alice queries for “Hey
Jude”
3) Alice requests file from
Bob or sever
1
3
1
2
1
Alice
Introduction
1-176
P2P: problems with centralized directory
Single point of failure
Performance
bottleneck
Copyright
infringement
file transfer is
decentralized, but
locating content is
highly centralized
Muti-server
Introduction
1-177
Query flooding: Gnutella
fully distributed
no central server
public domain protocol
many Gnutella clients
implementing protocol
overlay network: graph
edge between peer X
and Y if there’s a TCP
connection
all active peers and
edges is overlay net
Edge is not a physical
link
Given peer will
typically be connected
with < 10 overlay
neighbors
Introduction
1-178
Gnutella: protocol
Query message
sent over existing TCP
connections
peers forward
Query message
QueryHit
sent over
reverse
Query
path
File transfer:
HTTP
Query
QueryHit
QueryHit
Scalability:
limited scope
flooding:TTL
Introduction
1-179
Gnutella: Peer joining
Joining peer X must find some other peer in
Gnutella network: use list of candidate peers
2. X sequentially attempts to make TCP with peers
on list until connection setup with Y
3. X sends Ping message to Y; Y forwards Ping
message.
4. All peers receiving Ping message respond with
Pong message
5. X receives many Pong messages. It can then
setup additional TCP connections
Peer leaving: see homework problem 16.
1.
Introduction
1-180
Exploiting heterogeneity: KaZaA
Each peer is either a
group leader or assigned
to a group leader.
TCP connection between
peer and its group leader.
TCP connections between
some pairs of group
leaders.
Group leader tracks the
content in all its
children.
ordinary peer
group-leader peer
neighoring relationships
in overlay network
Introduction
1-181
KaZaA: Querying
Each file has a hash and a descriptor
Client sends keyword query to its group
leader
Group leader responds with matches:
For each match: metadata, hash, IP address
If group leader forwards query to other
group leaders, they respond with matches
Client then selects files for downloading
HTTP requests using hash as identifier sent to
peers holding desired file
Introduction
1-182
KaZaA tricks
Limitations on simultaneous uploads
Request queuing
Incentive priorities
Parallel downloading
For more info:
J. Liang, R. Kumar, K. Ross, “Understanding KaZaA,”
(available via cis.poly.edu/~ross)
Introduction
1-183
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-184
Socket programming
Goal: learn how to build client/server application that
communicate using sockets
Socket API
introduced in BSD4.1 UNIX,
1981
explicitly created, used,
released by apps
client/server paradigm
two types of transport
service via socket API:
unreliable datagram
reliable, byte streamoriented
socket
a host-local,
application-created,
OS-controlled interface
(a “door”) into which
application process can
both send and
receive messages to/from
another application
process
Introduction
1-185
Socket-programming using TCP
Socket: a door between application process and endend-transport protocol (UCP or TCP)
TCP service: reliable transfer of bytes from one
process to another
controlled by
application
developer
controlled by
operating
system
process
process
socket
TCP with
buffers,
variables
host or
server
internet
socket
TCP with
buffers,
variables
controlled by
application
developer
controlled by
operating
system
host or
server
Introduction
1-186
Socket programming with TCP
Client must contact server
server process must first
be running
server must have created
socket (door) that
welcomes client’s contact
Client contacts server by:
creating client-local TCP
socket
specifying IP address, port
number of server process
When client creates
socket: client TCP
establishes connection to
server TCP
When contacted by client,
server TCP creates new
socket for server process to
communicate with client
allows server to talk with
multiple clients
source port numbers
used to distinguish
clients (more in Chap 3)
application viewpoint
TCP provides reliable, in-order
transfer of bytes (“pipe”)
between client and server
Introduction
1-187
Client/server socket interaction: TCP
Server (running on hostid)
Client
create socket,
port=x, for
incoming request:
welcomeSocket =
ServerSocket()
TCP
wait for incoming
connection request connection
connectionSocket =
welcomeSocket.accept()
read request from
connectionSocket
write reply to
connectionSocket
close
connectionSocket
setup
create socket,
connect to hostid, port=x
clientSocket =
Socket()
send request using
clientSocket
read reply from
clientSocket
close
clientSocket
Introduction
1-188
Stream jargon
keyboard
monitor
output
stream
inFromServer
Client
Process
process
input
stream
outToServer
characters that flow into
or out of a process.
An input stream is
attached to some input
source for the process,
e.g., keyboard or socket.
An output stream is
attached to an output
source, e.g., monitor or
socket.
inFromUser
A stream is a sequence of
input
stream
client
TCP
clientSocket
socket
to network
TCP
socket
from network
Introduction
1-189
Socket programming with TCP
Example client-server app:
1) client reads line from
standard input (inFromUser
stream) , sends to server via
socket (outToServer
stream)
2) server reads line from socket
3) server converts line to
uppercase, sends back to
client
4) client reads, prints modified
line from socket
(inFromServer stream)
Introduction
1-190
Example: Java client (TCP)
import java.io.*;
import java.net.*;
class TCPClient {
public static void main(String argv[]) throws Exception
{
String sentence;
String modifiedSentence;
Create
input stream
Create
client socket,
connect to server
Create
output stream
attached to socket
BufferedReader inFromUser =
new BufferedReader(new InputStreamReader(System.in));
Socket clientSocket = new Socket("hostname", 6789);
DataOutputStream outToServer =
new DataOutputStream(clientSocket.getOutputStream());
Introduction
1-191
Example: Java client (TCP), cont.
Create
input stream
attached to socket
BufferedReader inFromServer =
new BufferedReader(new
InputStreamReader(clientSocket.getInputStream()));
sentence = inFromUser.readLine();
Send line
to server
outToServer.writeBytes(sentence + '\n');
Read line
from server
modifiedSentence = inFromServer.readLine();
System.out.println("FROM SERVER: " + modifiedSentence);
clientSocket.close();
}
}
Introduction
1-192
Example: Java server (TCP)
import java.io.*;
import java.net.*;
class TCPServer {
Create
welcoming socket
at port 6789
Wait, on welcoming
socket for contact
by client
Create input
stream, attached
to socket
public static void main(String argv[]) throws Exception
{
String clientSentence;
String capitalizedSentence;
ServerSocket welcomeSocket = new ServerSocket(6789);
while(true) {
Socket connectionSocket = welcomeSocket.accept();
BufferedReader inFromClient =
new BufferedReader(new
InputStreamReader(connectionSocket.getInputStream()));
Introduction
1-193
Example: Java server (TCP), cont
Create output
stream, attached
to socket
DataOutputStream outToClient =
new DataOutputStream(connectionSocket.getOutputStream());
Read in line
from socket
clientSentence = inFromClient.readLine();
capitalizedSentence = clientSentence.toUpperCase() + '\n';
Write out line
to socket
outToClient.writeBytes(capitalizedSentence);
}
}
}
End of while loop,
loop back and wait for
another client connection
Introduction
1-194
Example: C++ server(TCP)
int main()
{
WSADATA wsd;
SOCKET sockListen,sockData;
if( WSAStartup(MAKEWORD(2,2), &wsd)!=NO_ERROR)
return 1;
sockListen=socket(PF_INET,SOCK_STREAM,IPPROTO_TCP);
struct sockaddr_in addr;
addr.sin_family = AF_INET;
addr.sin_port = htons(6789);
addr.sin_addr.s_addr = INADDR_ANY;
if(bind(sockListen, (struct sockaddr *)&addr,
sizeof(struct sockaddr)) == SOCKET_ERROR)
return 1;
Introduction
1-195
Example: C++ server(TCP ), cont
if(listen(sockListen,1)==SOCKET_ERROR)
return 1;
while(true)
{
sockData=accept(sockListen,NULL,NULL);
char recvbuf[1024] = "From Server:";
int bytesRecv=recv( sockData, recvbuf+12, 1000, 0 );
cout<<"From Client:" <<recvbuf+12<<endl;
send(sockData,recvbuf,bytesRecv+12,0);
}
WSACleanup();
}
//ws2_32.lib
Introduction
1-196
Example: C++ client(TCP)
int main()
{
WSADATA wsd;
SOCKET sockClient;
if( WSAStartup(MAKEWORD(2,2), &wsd)!=NO_ERROR)
return 1;
sockClient=socket(PF_INET,SOCK_STREAM,IPPROTO_TCP);
struct sockaddr_in addr;
addr.sin_family = AF_INET;
addr.sin_port = htons(6789);
addr.sin_addr.s_addr = inet_addr( "127.0.0.1" );
if ( connect( sockClient, (SOCKADDR*) &addr, sizeof(addr) )
== SOCKET_ERROR) {
cout<<"Failed to connect."<<endl;
return 1;
}
Introduction
1-197
Example: C++ client(TCP ), cont
}
char recvbuf[1024] ="";
string s;
while(true)
{
getline(cin,s);
send(sockClient,s.c_str(),s.size(),0);
int bytesRecv = recv(sockClient, recvbuf,
1024, 0 );
cout<<recvbuf<<endl;
}
WSACleanup();
Introduction
1-198
Chapter 2: Application layer
2.1 Principles of
network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-199
Socket programming with UDP
UDP: no “connection” between
client and server
no handshaking
sender explicitly attaches
IP address and port of
destination to each packet
server must extract IP
address, port of sender
from received packet
application viewpoint
UDP provides unreliable transfer
of groups of bytes (“datagrams”)
between client and server
UDP: transmitted data may be
received out of order, or
lost
Introduction
1-200
Client/server socket interaction: UDP
Server (running on hostid)
create socket,
port=x, for
incoming request:
serverSocket =
DatagramSocket()
read request from
serverSocket
write reply to
serverSocket
specifying client
host address,
port number
Client
create socket,
clientSocket =
DatagramSocket()
Create, address (hostid, port=x,
send datagram request
using clientSocket
read reply from
clientSocket
close
clientSocket
Introduction
1-201
Example: Java client (UDP)
input
stream
Client
process
monitor
inFromUser
keyboard
Process
Input: receives
packet (recall
thatTCP received
“byte stream”)
UDP
packet
receivePacket
packet (recall
that TCP sent
“byte stream”)
sendPacket
Output: sends
UDP
packet
client
UDP
clientSocket
socket
to network
UDP
socket
from network
Introduction
1-202
Example: Java client (UDP)
import java.io.*;
import java.net.*;
Create
input stream
Create
client socket
Translate
hostname to IP
address using DNS
class UDPClient {
public static void main(String args[]) throws Exception
{
BufferedReader inFromUser =
new BufferedReader(new InputStreamReader(System.in));
DatagramSocket clientSocket = new DatagramSocket();
InetAddress IPAddress = InetAddress.getByName("hostname");
byte[] sendData = new byte[1024];
byte[] receiveData = new byte[1024];
String sentence = inFromUser.readLine();
sendData = sentence.getBytes();
Introduction
1-203
Example: Java client (UDP), cont.
Create datagram
with data-to-send,
length, IP addr, port
DatagramPacket sendPacket =
new DatagramPacket(sendData, sendData.length, IPAddress, 9876);
Send datagram
to server
clientSocket.send(sendPacket);
Read datagram
from server
clientSocket.receive(receivePacket);
DatagramPacket receivePacket =
new DatagramPacket(receiveData, receiveData.length);
String modifiedSentence =
new String(receivePacket.getData());
System.out.println("FROM SERVER:" + modifiedSentence);
clientSocket.close();
}
}
Introduction
1-204
Example: Java server (UDP)
import java.io.*;
import java.net.*;
Create
datagram socket
at port 9876
class UDPServer {
public static void main(String args[]) throws Exception
{
DatagramSocket serverSocket = new DatagramSocket(9876);
byte[] receiveData = new byte[1024];
byte[] sendData = new byte[1024];
while(true)
{
Create space for
received datagram
Receive
datagram
DatagramPacket receivePacket =
new DatagramPacket(receiveData, receiveData.length);
serverSocket.receive(receivePacket);
Introduction
1-205
Example: Java server (UDP), cont
String sentence = new String(receivePacket.getData());
Get IP addr
port #, of
sender
InetAddress IPAddress = receivePacket.getAddress();
int port = receivePacket.getPort();
String capitalizedSentence = sentence.toUpperCase();
sendData = capitalizedSentence.getBytes();
Create datagram
to send to client
DatagramPacket sendPacket =
new DatagramPacket(sendData, sendData.length, IPAddress,
port);
Write out
datagram
to socket
serverSocket.send(sendPacket);
}
}
}
End of while loop,
loop back and wait for
another datagram
Introduction
1-206
Example: C++ client (UDP)
int main()
{
WSADATA wsd;
SOCKET sockClient;
if( WSAStartup(MAKEWORD(2,2), &wsd)!=NO_ERROR)
return 1;
sockClient=socket(PF_INET,SOCK_DGRAM,
IPPROTO_UDP);
struct sockaddr_in addr;
addr.sin_family = AF_INET;
addr.sin_port = htons(6789);
addr.sin_addr.s_addr = inet_addr( "127.0.0.1" );
Introduction
1-207
Example: C++ client (UDP), cont
}
while(true)
{
char recvbuf[1024] ="";
int SenderAddrSize=sizeof(struct sockaddr);
string s;
getline(cin,s);
int nRet=sendto(sockClient,
s.c_str(),s.size(), 0,
(SOCKADDR *) &addr, sizeof(addr));
int bytesRecv = recvfrom(sockClient, recvbuf, 1024, 0
,(SOCKADDR *) &addr, &SenderAddrSize);
cout<<recvbuf<<endl;
}
closesocket(sockClient);
WSACleanup();
Introduction
1-208
Example: C++ server (UDP)
int main()
{
WSADATA wsd;
SOCKET sockListen;
if( WSAStartup(MAKEWORD(2,2), &wsd)!=NO_ERROR)
return 1;
sockListen=socket(PF_INET,SOCK_DGRAM, IPPROTO_UDP);
struct sockaddr_in addr;
addr.sin_family = AF_INET;
addr.sin_port = htons(6789);
addr.sin_addr.s_addr =htonl(INADDR_ANY);
if(bind(sockListen, (struct sockaddr *)&addr,
sizeof(struct sockaddr)) == SOCKET_ERROR)
return 1;
Introduction
1-209
Example: C++ server (UDP ), cont
while(true)
{
int SenderAddrSize=sizeof(struct sockaddr);
struct sockaddr_in addr_src;
char recvbuf[1024] = "From Server:";
int bytesRecv=recvfrom( sockListen, recvbuf+12, 1000,
MSG_PARTIAL ,(SOCKADDR *)&addr_src,&SenderAddrSize);
cout<<"From Client:" <<recvbuf+12<<endl;
sendto(sockListen,recvbuf,bytesRecv+12,0,
(SOCKADDR* )&addr_src,sizeof(struct sockaddr));
}
}
closesocket(sockListen);
WSACleanup();
Introduction
1-210
Chapter 2: Application layer
2.1 Principles of
network applications
app architectures
app requirements
2.2 Web and HTTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P file sharing
2.7 Socket programming
with TCP
2.8 Socket programming
with UDP
2.9 Building a Web
server
Introduction
1-211
Building a simple Web server
handles one HTTP
request
accepts the request
parses header
obtains requested file
from server’s file
system
creates HTTP response
message:
after creating server,
you can request file
using a browser (e.g.,
IE explorer)
header lines + file
sends response to client
Introduction
1-212
Chapter 2: Summary
Our study of network apps now complete!
Application architectures
client-server
P2P
hybrid
application service
requirements:
specific protocols:
HTTP
FTP
SMTP, POP, IMAP
DNS
socket programming
reliability, bandwidth,
delay
Internet transport
service model
connection-oriented,
reliable: TCP
unreliable, datagrams: UDP
Introduction
1-213
Chapter 2: Summary
Most importantly: learned about protocols
typical request/reply
message exchange:
client requests info or
service
server responds with
data, status code
message formats:
headers: fields giving
info about data
data: info being
communicated
control vs. data msgs
in-band, out-of-band
centralized vs. decentralized
stateless vs. stateful
reliable vs. unreliable msg
transfer
“complexity at network
edge”
Introduction
1-214
Programming Assignments
Multi-Threaded Web Server
Email Client
UDP Pinger Lab
Web Proxy Server
Ftp client
Instant Messager
DDNS
Introduction
1-215
Ethereal Labs
HTTP
DNS
FTP
Homework problems
1 4 9 13 16
Introduction
1-216
Chapter 3: Transport Layer
Our goals:
understand principles
behind transport
layer services:
multiplexing/demultipl
exing
reliable data transfer
flow control
congestion control
learn about transport
layer protocols in the
Internet:
UDP: connectionless
transport
TCP: connection-oriented
transport
TCP congestion control
Introduction
1-217
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-218
Transport services and protocols
provide logical communication
between app processes
running on different hosts
transport protocols run in
end systems
send side: breaks app
messages into segments,
passes to network layer
rcv side: reassembles
segments into messages,
passes to app layer
more than one transport
protocol available to apps
Internet: TCP and UDP
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Introduction
1-219
Transport vs. network layer
network layer: logical
communication
between hosts
transport layer: logical
communication
between processes
relies on, enhances,
network layer services
NAT
Who is host?
How to identify NAT?
Household analogy:
12 kids sending letters to
12 kids
processes = kids
app messages = letters
in envelopes
hosts = houses
transport protocol =
Ann and Bill
network-layer protocol
= postal service
Introduction
1-220
Internet transport-layer protocols
reliable, in-order delivery
,TCP(Transmission Control
protocol)
congestion control
flow control
connection setup
unreliable, unordered
delivery: UDP(User
Datagram protocol)
no-frills extension of “besteffort” IP , effective usually
services not available:
delay guarantees
bandwidth guarantees
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Introduction
1-221
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-222
Multiplexing/demultiplexing
Multiplexing at send host:
gathering data from multiple
sockets, enveloping data with
header (later used for
demultiplexing)
Demultiplexing at rcv host:
delivering received segments
to correct socket
= socket
application
transport
network
link
= process
P3
P1
P1
application
transport
network
P2
P4
application
transport
network
link
link
physical
host 1
physical
host 2
physical
host 3
Introduction
1-223
How demultiplexing works
host receives IP datagrams
each datagram has source
IP address, destination IP
address
each datagram carries 1
transport-layer segment
each segment has source,
destination port number
host uses IP addresses & port
numbers to direct segment to
appropriate socket
32 bits
source port #
dest port #
other header fields
application
data
(message)
TCP/UDP segment format
Introduction
1-224
Connectionless demultiplexing
Create sockets with port
numbers:
UDP socket identified by
two-tuple:
DatagramSocket mySocket1 = new (dest IP address, dest port number)
DatagramSocket(12534);
When host receives UDP
DatagramSocket mySocket2 = new
segment:
DatagramSocket(12535);
checks destination port
number in segment
struct sockaddr_in addr;
directs UDP segment to socket
with that port number
addr.sin_family = AF_INET;
addr.sin_port = htons(6789);
addr.sin_addr.s_addr =
INADDR_ANY
Bind(sock, &addr
sizeof(sockaddr));
IP datagrams with different
source IP addresses and/or
source port numbers directed
to same socket
Introduction
1-225
Connectionless demux (cont)
DatagramSocket serverSocket = new DatagramSocket(6428);
P2
SP: 6428
SP: 6428
DP: 9157
DP: 5775
SP: 9157
client
IP: A
P1
P1
P3
DP: 6428
SP: 5775
server
IP: C
DP: 6428
Client
IP:B
SP provides “return address”
Introduction
1-226
Connection-oriented demux
TCP socket identified
by 4-tuple:
source IP address
source port number
dest IP address
dest port number
recv host uses all four
values to direct
segment to appropriate
socket
Server host may support
many simultaneous TCP
sockets:
each socket identified by
its own 4-tuple
Web servers have
different sockets for
each connecting client
non-persistent HTTP will
have different socket for
each request
Introduction
1-227
Connection-oriented demux
sockData=accept(sockListen,NULL,NULL);
int bytesRecv=recv( sockData, recvbuf+12, 1000, 0 );
send(sockData,recvbuf,bytesRecv+12,0);
ServerSocket welcomeSocket = new
ServerSocket(6789);
Socket connectionSocket =
welcomeSocket.accept();
Introduction
1-228
Connection-oriented demux
(cont)
P1
P4
P5
P2
P6
P1P3
SP: 5775
DP: 80
S-IP: B
D-IP:C
SP: 9157
client
IP: A
DP: 80
S-IP: A
D-IP:C
SP: 9157
server
IP: C
DP: 80
S-IP: B
D-IP:C
Client
IP:B
Introduction
1-229
Connection-oriented demux:
Threaded Web Server
P1
P2
P4
P1P3
SP: 5775
DP: 80
S-IP: B
D-IP:C
SP: 9157
client
IP: A
DP: 80
S-IP: A
D-IP:C
SP: 9157
server
IP: C
DP: 80
S-IP: B
D-IP:C
Client
IP:B
Introduction
1-230
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-231
UDP: User Datagram Protocol [RFC 768]
“no frills,” “bare bones”
Internet transport
protocol
“best effort” service, UDP
segments may be:
lost
delivered out of order
to app
connectionless:
no handshaking between
UDP sender, receiver
each UDP segment
handled independently
of others
Why is there a UDP?
no connection
establishment (which can
add delay)
simple: no connection state
at sender, receiver
small segment header
8 Bytes vs 20Bytes
no congestion control: UDP
can blast away as fast as
desired
Introduction
1-232
UDP: more
often used for streaming
multimedia apps
loss tolerant
rate sensitive
other UDP uses
DNS
SNMP
Length, in
bytes of UDP
segment,
including
header
RIP
Figure 3.6
reliable transfer over UDP:
add reliability at application
layer
application-specific error
recovery!
32 bits
source port #
dest port #
length
checksum
Application
data
(message)
UDP segment format
Introduction
1-233
UDP checksum
Goal: detect “errors” (e.g., flipped bits) in transmitted
segment
etc. barcode , credit card
Sender:
Receiver:
treat segment contents
as sequence of 16-bit
integers
checksum: addition (1’s
complement sum) of
segment contents
sender puts checksum
value into UDP checksum
field
compute checksum of
received segment
check if computed checksum
equals checksum field value:
NO - error detected
YES - no error detected.
But maybe errors
nonetheless? More later
….
Introduction
1-234
Internet Checksum Example
Note
When adding numbers, a carryout from the most
significant bit needs to be added to the result
Do Many layer protocol provide error checksum?
why?
Example: add two 16-bit integers
1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
sum 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
checksum 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
Introduction
1-235
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-236
Principles of Reliable data transfer
important in app., transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
Introduction
1-237
Principles of Reliable data transfer
important in app., transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
Introduction
1-238
Principles of Reliable data transfer
important in app., transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
Introduction
1-239
Reliable data transfer: getting started
rdt_send(): called from above,
(e.g., by app.). Passed data to
deliver to receiver upper layer
send
side
udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver
deliver_data(): called by
rdt to deliver data to upper
receive
side
rdt_rcv(): called when packet
arrives on rcv-side of channel
Introduction
1-240
Reliable data transfer: getting started
We’ll:
incrementally develop sender, receiver sides of
reliable data transfer protocol (rdt)
consider only unidirectional data transfer
but control info will flow on both directions!
use finite state machines (FSM) to specify
sender, receiver
state: when in this
“state” next state
uniquely determined
by next event
state
1
event causing state transition
actions taken on state transition
event
actions
state
2
Introduction
1-241
Rdt1.0: reliable transfer over a reliable channel
underlying channel perfectly reliable
no bit errors
no loss of packets
separate FSMs for sender, receiver:
sender sends data into underlying channel
receiver read data from underlying channel
Wait for
call from
above
rdt_send(data)
packet = make_pkt(data)
udt_send(packet)
sender
Wait for
call from
below
rdt_rcv(packet)
extract (packet,data)
deliver_data(data)
receiver
Introduction
1-242
Rdt2.0: channel with bit errors
underlying channel may flip bits in packet
checksum to detect bit errors
the question: how to recover from errors:
acknowledgements (ACKs): receiver explicitly tells sender
that pkt received OK
negative acknowledgements (NAKs): receiver explicitly
tells sender that pkt had errors
sender retransmits pkt on receipt of NAK
new mechanisms in rdt2.0 (beyond rdt1.0):
error detection
receiver feedback: control msgs (ACK,NAK) rcvr->sender
Introduction
1-243
rdt2.0: FSM specification
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
sender
receiver
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Introduction
1-244
rdt2.0: operation with no errors
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Introduction
1-245
rdt2.0: error scenario
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Introduction
1-246
rdt2.0 has a fatal flaw!
What happens if
ACK/NAK corrupted?
sender doesn’t know what
happened at receiver!
can’t just retransmit:
possible duplicate
Handling duplicates:
sender retransmits current
pkt if ACK/NAK garbled
sender adds sequence
number to each pkt
receiver discards (doesn’t
deliver up) duplicate pkt
stop and wait
Sender sends one packet,
then waits for receiver
response
Introduction
1-247
rdt2.1: sender, handles garbled ACK/NAKs
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait
for
Wait for
isNAK(rcvpkt) )
ACK or
call 0 from
udt_send(sndpkt)
NAK 0
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isNAK(rcvpkt) )
udt_send(sndpkt)
L
Wait for
ACK or
NAK 1
Wait for
call 1 from
above
rdt_send(data)
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
Introduction
1-248
rdt2.1: receiver, handles garbled ACK/NAKs
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq1(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
Wait for
0 from
below
Wait for
1 from
below
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
Introduction
1-249
rdt2.1: discussion
Sender:
seq # added to pkt
two seq. #’s (0,1) will
suffice. Why?
must check if received
ACK/NAK corrupted
twice as many states
state must “remember”
whether “current” pkt
has 0 or 1 seq. #
Receiver:
must check if received
packet is duplicate
state indicates whether
0 or 1 is expected pkt
seq #
note: receiver can not
know if its last
ACK/NAK received OK
at sender
Introduction
1-250
rdt2.2: a NAK-free protocol
same functionality as rdt2.1, using ACKs only
instead of NAK, receiver sends ACK for last pkt
received OK
receiver must explicitly include seq # of pkt being ACKed
duplicate ACK at sender results in same action as
NAK: retransmit current pkt
Introduction
1-251
rdt2.2: sender, receiver fragments
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait for
Wait for
isACK(rcvpkt,1) )
ACK
call 0 from
0
udt_send(sndpkt)
above
sender FSM
fragment
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
has_seq1(rcvpkt))
udt_send(sndpkt)
Wait for
0 from
below
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
receiver FSM
fragment
L
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt)
Introduction
1-252
rdt3.0: channels with errors and loss
New assumption:
underlying channel can
also lose packets (data
or ACKs)
checksum, seq. #, ACKs,
retransmissions will be
of help, but not enough
Approach: sender waits
“reasonable” amount of
time for ACK
retransmits if no ACK
received in this time
if pkt (or ACK) just delayed
(not lost):
retransmission will be
duplicate, but use of seq.
#’s already handles this
receiver must specify seq
# of pkt being ACKed
requires countdown timer
Introduction
1-253
rdt3.0 sender
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
L
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,1)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,0) )
timeout
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
stop_timer
stop_timer
timeout
udt_send(sndpkt)
start_timer
L
Wait
for
ACK0
Wait for
call 0from
above
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
Wait
for
ACK1
Wait for
call 1 from
above
rdt_send(data)
rdt_rcv(rcvpkt)
L
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
start_timer
Introduction
1-254
rdt3.0 in action
Introduction
1-255
rdt3.0 in action
Introduction
1-256
Performance of rdt3.0
rdt3.0 works, but performance stinks
example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:
Ttransmit =
L (packet length in bits)
8kb/pkt
=
= 8 microsec
R (transmission rate, bps)
10**9 b/sec
U sender: utilization – fraction of time sender busy sending
U
sender
=
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link
network protocol limits use of physical resources!
Introduction
1-257
rdt3.0: stop-and-wait operation
sender
receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
U
=
sender
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
Introduction
1-258
Pipelined protocols
Pipelining: sender allows multiple, “in-flight”, yet-tobe-acknowledged pkts
range of sequence numbers must be increased
buffering at sender and/or receiver
Two generic forms of pipelined protocols: go-Back-N,
selective repeat
Introduction
1-259
Pipelining: increased utilization
sender
receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
Increase utilization
by a factor of 3!
U
sender
=
3*L/R
RTT + L / R
=
.024
30.008
= 0.0008
microsecon
ds
Introduction
1-260
Go-Back-N
Sender:
k-bit seq # in pkt header
“window” of up to N, consecutive unack’ed pkts allowed
ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”
may receive duplicate ACKs (see receiver)
timer for each in-flight pkt
timeout(n): retransmit pkt n and all higher seq # pkts in window
Introduction
1-261
GBN: sender extended FSM
rdt_send(data)
L
base=1
nextseqnum=1
if (nextseqnum < base+N) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)
udt_send(sndpkt[nextseqnum])
if (base == nextseqnum)
start_timer
nextseqnum++
}
else
refuse_data(data)
Wait
rdt_rcv(rcvpkt)
&& corrupt(rcvpkt)
timeout
start_timer
udt_send(sndpkt[base])
udt_send(sndpkt[base+1])
…
udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1
If (base == nextseqnum)
stop_timer
else
start_timer
Introduction
1-262
GBN: receiver extended FSM
default
udt_send(sndpkt)
L
Wait
expectedseqnum=1
sndpkt =
make_pkt(expectedseqnum,ACK,chksum)
rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++
ACK-only: always send ACK for correctly-received pkt
with highest in-order seq #
may generate duplicate ACKs
need only remember expectedseqnum
out-of-order pkt:
discard (don’t buffer) -> no receiver buffering!
Re-ACK pkt with highest in-order seq #
Introduction
1-263
GBN in
action
Introduction
1-264
Selective Repeat
receiver individually acknowledges all correctly
received pkts
buffers pkts, as needed, for eventual in-order delivery
to upper layer
sender only resends pkts for which ACK not
received
sender timer for each unACKed pkt
sender window
N consecutive seq #’s
again limits seq #s of sent, unACKed pkts
Introduction
1-265
Selective repeat: sender, receiver windows
Introduction
1-266
Selective repeat
sender
data from above :
receiver
pkt n in [rcvbase, rcvbase+N-1]
if next available seq # in
send ACK(n)
timeout(n):
in-order: deliver (also
window, send pkt
resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N]:
mark pkt n as received
if n smallest unACKed pkt,
advance window base to
next unACKed seq #
out-of-order: buffer
deliver buffered, in-order
pkts), advance window to
next not-yet-received pkt
pkt n in
[rcvbase-N,rcvbase-1]
ACK(n)
otherwise:
ignore
Introduction
1-267
Selective repeat in action
Introduction
1-268
Selective repeat:
dilemma
Example:
seq #’s: 0, 1, 2, 3
window size=3
receiver sees no
difference in two
scenarios!
incorrectly passes
duplicate data as new
in (a)
Q: what relationship
between seq # size
and window size?
Introduction
1-269
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-270
TCP: Overview
point-to-point:
one sender, one receiver
reliable, in-order byte
steam:
no “message boundaries”
pipelined:
TCP congestion and flow
control set window size
send & receive buffers
socket
door
application
writes data
application
reads data
TCP
send buffer
TCP
receive buffer
RFCs: 793, 1122, 1323, 2018, 2581
full duplex data:
bi-directional data flow
in same connection
MSS: maximum segment
size
connection-oriented:
handshaking (exchange
of control msgs) init’s
sender, receiver state
before data exchange
flow controlled:
sender will not
socket
door
overwhelm receiver
segment
Introduction
1-271
TCP segment structure
32 bits
URG: urgent data
(generally not used)
ACK: ACK #
valid
PSH: push data now
(generally not used)
RST, SYN, FIN:
connection estab
(setup, teardown
commands)
Internet
checksum
(as in UDP)
source port #
dest port #
sequence number
acknowledgement number
head not
UA P R S F
len used
checksum
Receive window
Urg data pnter
Options (variable length)
counting
by bytes
of data
(not segments!)
# bytes
rcvr willing
to accept
application
data
(variable length)
Introduction
1-272
TCP seq. #’s and ACKs
Seq. #’s:
byte stream
“number” of first
byte in segment’s
data
ACKs:
seq # of next byte
expected from
other side
cumulative ACK
Q: how receiver handles
out-of-order segments
A: TCP spec doesn’t
say, - up to
implementor
Host A
User
types
‘C’
Host B
host ACKs
receipt of
‘C’, echoes
back ‘C’
host ACKs
receipt
of echoed
‘C’
simple telnet scenario
Introduction
time
1-273
TCP Round Trip Time and Timeout
Q: how to set TCP
timeout value?
longer than RTT
but RTT varies
too short: premature
timeout
unnecessary
retransmissions
too long: slow reaction
to segment loss
Q: how to estimate RTT?
SampleRTT: measured time from
segment transmission until ACK
receipt
ignore retransmissions
SampleRTT will vary, want
estimated RTT “smoother”
average several recent
measurements, not just
current SampleRTT
Introduction
1-274
TCP Round Trip Time and Timeout
EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT
Exponential weighted moving average
influence of past sample decreases exponentially fast
typical value: = 0.125
Introduction
1-275
Example RTT estimation:
RTT: gaia.cs.umass.edu to fantasia.eurecom.fr
350
RTT (milliseconds)
300
250
200
150
100
1
8
15
22
29
36
43
50
57
64
71
78
85
92
99
106
time (seconnds)
SampleRTT
Estimated RTT
Introduction
1-276
TCP Round Trip Time and Timeout
Setting the timeout
EstimtedRTT plus “safety margin”
large variation in EstimatedRTT -> larger safety margin
first estimate of how much SampleRTT deviates from
EstimatedRTT:
DevRTT = (1-)*DevRTT +
*|SampleRTT-EstimatedRTT|
(typically, = 0.25)
Then set timeout interval:
TimeoutInterval = EstimatedRTT + 4*DevRTT
Introduction
1-277
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-278
TCP reliable data transfer
TCP creates rdt
service on top of IP’s
unreliable service
Pipelined segments
Cumulative acks
TCP uses single
retransmission timer
Retransmissions are
triggered by:
timeout events
duplicate acks
Initially consider
simplified TCP sender:
ignore duplicate acks
ignore flow control,
congestion control
Introduction
1-279
TCP sender events:
data rcvd from app:
Create segment with
seq #
seq # is byte-stream
number of first data
byte in segment
start timer if not
already running (think
of timer as for oldest
unacked segment)
expiration interval:
TimeOutInterval
timeout:
retransmit segment
that caused timeout
restart timer
Ack rcvd:
If acknowledges
previously unacked
segments
update what is known to
be acked
start timer if there are
outstanding segments
Introduction
1-280
NextSeqNum = InitialSeqNum
SendBase = InitialSeqNum
loop (forever) {
switch(event)
event: data received from application above
create TCP segment with sequence number NextSeqNum
if (timer currently not running)
start timer
pass segment to IP
NextSeqNum = NextSeqNum + length(data)
event: timer timeout
retransmit not-yet-acknowledged segment with
smallest sequence number
start timer
event: ACK received, with ACK field value of y
if (y > SendBase) {
SendBase = y
if (there are currently not-yet-acknowledged segments)
start timer
}
} /* end of loop forever */
TCP
sender
(simplified)
Comment:
• SendBase-1: last
cumulatively
ack’ed byte
Example:
• SendBase-1 = 71;
y= 73, so the rcvr
wants 73+ ;
y > SendBase, so
that new data is
acked
Introduction
1-281
TCP: retransmission scenarios
Host A
X
loss
Sendbase
= 100
SendBase
= 120
SendBase
= 100
time
SendBase
= 120
lost ACK scenario
Host B
Seq=92 timeout
Host B
Seq=92 timeout
timeout
Host A
time
premature timeout
Introduction
1-282
TCP retransmission scenarios (more)
timeout
Host A
Host B
X
loss
SendBase
= 120
time
Cumulative ACK scenario
Introduction
1-283
TCP ACK generation
[RFC 1122, RFC 2581]
Event at Receiver
TCP Receiver action
Arrival of in-order segment with
expected seq #. All data up to
expected seq # already ACKed
Delayed ACK. Wait up to 500ms
for next segment. If no next segment,
send ACK
Arrival of in-order segment with
expected seq #. One other
segment has ACK pending
Immediately send single cumulative
ACK, ACKing both in-order segments
Arrival of out-of-order segment
higher-than-expect seq. # .
Gap detected
Immediately send duplicate ACK,
indicating seq. # of next expected byte
Arrival of segment that
partially or completely fills gap
Immediate send ACK, provided that
segment startsat lower end of gap
Introduction
1-284
Fast Retransmit
Time-out period often
relatively long:
long delay before
resending lost packet
Detect lost segments
via duplicate ACKs.
Sender often sends
many segments back-toback
If segment is lost,
there will likely be many
duplicate ACKs.
If sender receives 3
ACKs for the same
data, it supposes that
segment after ACKed
data was lost:
fast retransmit: resend
segment before timer
expires
Introduction
1-285
Fast retransmit algorithm:
event: ACK received, with ACK field value of y
if (y > SendBase) {
SendBase = y
if (there are currently not-yet-acknowledged segments)
start timer
}
else {
increment count of dup ACKs received for y
if (count of dup ACKs received for y = 3) {
resend segment with sequence number y
}
a duplicate ACK for
already ACKed segment
fast retransmit
Introduction
1-286
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-287
TCP Flow Control
receive side of TCP
connection has a
receive buffer:
flow control
sender won’t overflow
receiver’s buffer by
transmitting too much,
too fast
speed-matching
app process may be
service: matching the
send rate to the
receiving app’s drain
rate
slow at reading from
buffer
Introduction
1-288
TCP Flow control: how it works
Rcvr advertises spare
(Suppose TCP receiver
discards out-of-order
segments)
spare room in buffer
room by including value
of RcvWindow in
segments
Sender limits unACKed
data to RcvWindow
guarantees receive
buffer doesn’t overflow
= RcvWindow
= RcvBuffer-[LastByteRcvd LastByteRead]
Introduction
1-289
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-290
TCP Connection Management
Recall: TCP sender, receiver
establish “connection”
before exchanging data
segments
initialize TCP variables:
seq. #s
buffers, flow control
info (e.g. RcvWindow)
client: connection initiator
Socket clientSocket = new
Socket("hostname","port
number");
server: contacted by client
Socket connectionSocket =
welcomeSocket.accept();
Three way handshake:
Step 1: client host sends TCP
SYN segment to server
specifies initial seq #
no data
Step 2: server host receives
SYN, replies with SYNACK
segment
server allocates buffers
specifies server initial
seq. #
Step 3: client receives SYNACK,
replies with ACK segment,
which may contain data
Introduction
1-291
TCP Connection Management (cont.)
Closing a connection:
client closes socket:
clientSocket.close();
client
close
Step 1: client end system
close
FIN, replies with ACK.
Closes connection, sends
FIN.
timed wait
sends TCP FIN control
segment to server
Step 2: server receives
server
closed
Introduction
1-292
TCP Connection Management (cont.)
Step 3: client receives FIN,
replies with ACK.
client
server
closing
Enters “timed wait” will respond with ACK
to received FINs
closing
Step 4: server, receives
Note: with small
modification, can handle
simultaneous FINs.
timed wait
ACK. Connection closed.
closed
closed
Introduction
1-293
TCP Connection Management (cont)
TCP server
lifecycle
TCP client
lifecycle
Introduction
1-294
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-295
Principles of Congestion Control
Congestion(阻塞):
informally: “too many sources sending too much
data too fast for network to handle”
different from flow control!
manifestations:
lost packets (buffer overflow at routers)
long delays (queueing in router buffers)
a top-10 problem!
Introduction
1-296
Causes/costs of congestion: scenario 1
Host A
two senders, two
receivers
one router,
infinite buffers
no retransmission
Host B
lout
lin : original data
unlimited shared
output link buffers
large delays
when congested
maximum
achievable
throughput
Introduction
1-297
Causes/costs of congestion: scenario 2
one router, finite buffers ->loss
sender retransmission of lost packet
Assume reliable transport service ->retransmit
Host A
Host B
lin : original
data
l'in : original data, plus
retransmitted data
lout
finite shared output
link buffers
Introduction
1-298
Causes/costs of congestion: scenario 2
(goodput)
= l
out
in
“perfect” retransmission only when loss:
always:
l
l > lout
in
retransmission of delayed (not lost) packet makes
(than perfect case) for same
R/2
l
in
lout
R/2
larger
R/2
lin
a.
R/2
lout
lout
lout
R/3
lin
b.
R/2
R/4
lin
R/2
c.
“costs” of congestion:
more work (retrans) for given “goodput”
unneeded retransmissions: link carries multiple copies of pkt
Introduction
1-299
Causes/costs of congestion: scenario 3
four senders
Q: what happens as l
in
and l increase ?
multihop paths
timeout/retransmit
in
Host A
lin : original data
lout
l'in : original data, plus
retransmitted data
finite shared output
link buffers
Host B
Introduction
1-300
Causes/costs of congestion: scenario 3
H
o
s
t
A
l
o
u
t
H
o
s
t
B
Another “cost” of congestion:
when packet dropped, any “upstream transmission
capacity used for that packet was wasted!
Introduction
1-301
Approaches towards congestion control
Two broad approaches towards congestion control:
End-end congestion
control:
no explicit feedback from
network
congestion inferred from
end-system observed loss,
delay
approach taken by TCP
Network-assisted
congestion control:
routers provide feedback
to end systems
single bit indicating
congestion (SNA,
DECbit, TCP/IP ECN,
ATM)
explicit rate sender
should send at
Introduction
1-302
Case study: ATM ABR congestion control
Asynchronous Transfer
Mode(异步传输模式)
ABR: available bit rate:
“elastic service”
if sender’s path
“underloaded”:
sender should use
available bandwidth
if sender’s path
congested:
sender throttled to
minimum guaranteed
rate
RM (resource management)
cells:
sent by sender, interspersed
with data cells
bits in RM cell set by switches
(“network-assisted”)
NI bit: no increase in rate
(mild congestion)
CI bit: congestion
indication
RM cells returned to sender by
receiver, with bits intact
Introduction
1-303
Case study: ATM ABR congestion control
two-byte ER (explicit rate) field in RM cell
congested switch may lower ER value in cell
sender’ send rate thus maximum supportable rate on path
EFCI bit in data cells: set to 1 in congested switch
if data cell preceding RM cell has EFCI set, sender sets CI
bit in returned RM cell
Introduction
1-304
Chapter 3 outline
3.1 Transport-layer
services
3.2 Multiplexing and
demultiplexing
3.3 Connectionless
transport: UDP
3.4 Principles of
reliable data transfer
3.5 Connection-oriented
transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of
congestion control
3.7 TCP congestion
control
Introduction
1-305
TCP Congestion Control: details
sender limits transmission:
LastByteSent-LastByteAcked
CongWin
Roughly,
rate =
CongWin
Bytes/sec
RTT
CongWin is dynamic, function
of perceived network
congestion
How does sender
perceive congestion?
loss event = timeout or
3 duplicate acks
TCP sender reduces
rate (CongWin) after
loss event
three mechanisms:
AIMD
slow start
conservative after
timeout events
Introduction
1-306
TCP congestion control:
additive increase,
multiplicative decrease
Approach: increase transmission rate (window size),
Saw tooth
behavior: probing
for bandwidth
congestion window size
probing for usable bandwidth, until loss occurs
additive increase: increase CongWin by 1 MSS
every RTT until loss detected
multiplicative decrease: cut CongWin in half after
loss
congestion
window
24 Kbytes
16 Kbytes
8 Kbytes
time
time
Introduction
1-307
TCP Slow Start
When connection begins,
CongWin = 1 MSS
Example: MSS = 500
bytes & RTT = 200 msec
initial rate = 20 kbps
When connection begins,
increase rate
exponentially fast until
first loss event
available bandwidth may
be >> MSS/RTT
desirable to quickly ramp
up to respectable rate
Introduction
1-308
TCP Slow Start (more)
When connection
Host B
RTT
begins, increase rate
exponentially until
first loss event:
Host A
double CongWin every
RTT
done by incrementing
CongWin for every ACK
received
Summary: initial rate
is slow but ramps up
exponentially fast
time
Introduction
1-309
Refinement
Q: When should the
exponential
increase switch to
linear?
A: When CongWin
gets to 1/2 of its
value before
timeout.
Implementation:
Variable Threshold
At loss event, Threshold is
set to 1/2 of CongWin just
before loss event
Introduction
1-310
Refinement: inferring loss
After 3 dup ACKs:
CongWin is cut in half
window then grows
linearly
But after timeout event:
CongWin instead set to
1 MSS;
window then grows
exponentially
to a threshold, then
grows linearly
Philosophy:
3 dup ACKs indicates
network capable of
delivering some segments
timeout indicates a
“more alarming”
congestion scenario
Introduction
1-311
Summary: TCP Congestion Control
When CongWin is below Threshold, sender in
slow-start phase, window grows exponentially.
When CongWin is above Threshold, sender is in
congestion-avoidance phase, window grows linearly.
When a triple duplicate ACK occurs, Threshold
set to CongWin/2 and CongWin set to
Threshold.
When timeout occurs, Threshold set to
CongWin/2 and CongWin is set to 1 MSS.
Introduction
1-312
TCP sender congestion control
State
Event
TCP Sender Action
Commentary
Slow Start
(SS)
ACK receipt
for previously
unacked
data
CongWin = CongWin +
CongWin ,
If (CongWin > Threshold)
set state to “Congestion
Avoidance”
Resulting in a doubling of
CongWin every RTT
Congestion
Avoidance
(CA)
ACK receipt
for previously
unacked
data
CongWin = CongWin+MSS
Additive increase, resulting
in increase of CongWin by
1 MSS every RTT
SS or CA
Loss event
detected by
triple
duplicate
ACK
Threshold = CongWin/2,
CongWin = Threshold,
Set state to “Congestion
Avoidance”
Fast recovery,
implementing multiplicative
decrease. CongWin will not
drop below 1 MSS.
SS or CA
Timeout
Threshold = CongWin/2,
CongWin = 1 MSS,
Set state to “Slow Start”
Enter slow start
SS or CA
Duplicate
ACK
Increment duplicate ACK count
for segment being acked
CongWin and Threshold not
changed
Introduction
1-313
TCP throughput
What’s the average throughout of TCP as a
function of window size and RTT?
Ignore slow start
Let W be the window size when loss occurs.
When window is W, throughput is W/RTT
Just after loss, window drops to W/2,
throughput to W/2RTT.
Average throughout: .75 W/RTT
Introduction
1-314
TCP Futures: TCP over “long, fat pipes”
Example: 1500 byte segments, 100ms RTT, want 10
Gbps throughput
Requires window size W = 83,333 in-flight
segments
Throughput in terms of loss rate L:
1.22 MSS
RTT L
➜ L = 2·10-10 Wow
New versions of TCP for high-speed needed!
Introduction
1-315
TCP Fairness
Fairness goal: if K TCP sessions share same
bottleneck link of bandwidth R, each should have
average rate of R/K
TCP connection 1
TCP
connection 2
bottleneck
router
capacity R
Introduction
1-316
Why is TCP fair?
Two competing sessions:
Additive increase gives slope of 1, as throughout increases
multiplicative decrease decreases throughput proportionally
R
equal bandwidth share
loss: decrease window by factor of 2
congestion avoidance: additive increase
loss: decrease window by factor of 2
congestion avoidance: additive increase
Connection 1 throughput R
Introduction
1-317
Fairness (more)
Fairness and UDP
Multimedia apps often
do not use TCP
do not want rate
throttled by congestion
control
Instead use UDP:
pump audio/video at
constant rate, tolerate
packet loss
Research area: TCP
friendly
Fairness and parallel TCP
connections
nothing prevents app from
opening parallel
connections between 2
hosts.
Web browsers do this
Example: link of rate R
supporting 9 cnctions;
new app asks for 1 TCP, gets
rate R/10
new app asks for 11 TCPs,
gets R/2 !
Introduction
1-318
Delay modeling
Q: How long does it take to
receive an object from a
Web server after sending
a request?
Ignoring congestion, delay is
influenced by:
TCP connection establishment
data transmission delay
slow start
Notation, assumptions:
Assume one link between
client and server of rate R
S: MSS (bits)
O: object size (bits)
no retransmissions (no loss,
no corruption)
Window size:
First assume: fixed
congestion window, W
segments
Then dynamic window,
modeling slow start
Introduction
1-319
Fixed congestion window (1)
First case:
WS/R > RTT + S/R: ACK for
first segment in window
returns before window’s
worth of data sent
delay = 2RTT + O/R
Introduction
1-320
Fixed congestion window (2)
Second case:
WS/R < RTT + S/R: wait
for ACK after sending
window’s worth of data
sent
delay = 2RTT + O/R
+ (K-1)[S/R + RTT - WS/R]
Introduction
1-321
TCP Delay Modeling: Slow Start (1)
Now suppose window grows according to slow start
Will show that the delay for one object is:
Latency 2 RTT
O
S
S
P RTT ( 2 P 1)
R
R
R
where P is the number of times TCP idles at server:
P min {Q, K 1}
- where Q is the number of times the server idles
if the object were of infinite size.
- and K is the number of windows that cover the object.
Introduction
1-322
TCP Delay Modeling: Slow Start (2)
Delay components:
• 2 RTT for connection
estab and request
• O/R to transmit
object
• time server idles due
to slow start
initiate TCP
connection
request
object
first window
= S/R
RTT
Server idles:
P = min{K-1,Q} times
Example:
• O/S = 15 segments
• K = 4 windows
•Q=2
• P = min{K-1,Q} = 2
Server idles P=2 times
second window
= 2S/R
third window
= 4S/R
fourth window
= 8S/R
complete
transmission
object
delivered
time at
client
time at
server
Introduction
1-323
TCP Delay Modeling (3)
S
RTT time from when server starts to send segment
R
until server receives acknowledg ement
initiate TCP
connection
2k 1
S
time to transmit the kth window
R
request
object
S
k 1 S
RTT
2
idle time after the kth window
R
R
first window
= S/R
RTT
second window
= 2S/R
third window
= 4S/R
P
O
delay 2 RTT idleTime p
R
p 1
P
O
S
S
2 RTT [ RTT 2 k 1 ]
R
R
k 1 R
O
S
S
2 RTT P[ RTT ] (2 P 1)
R
R
R
fourth window
= 8S/R
complete
transmission
object
delivered
time at
client
time at
server
Introduction
1-324
TCP Delay Modeling (4)
Recall K = number of windows that cover object
How do we calculate K ?
K min {k : 2 0 S 21 S 2 k 1 S O}
min {k : 2 0 21 2 k 1 O / S }
O
min {k : 2 1 }
S
O
min {k : k log 2 ( 1)}
S
O
log 2 ( 1)
S
k
Calculation of Q, number of idles for infinite-size object,
is similar (see HW).
Introduction
1-325
HTTP Modeling
Assume Web page consists of:
1 base HTML page (of size O bits)
M images (each of size O bits)
Non-persistent HTTP:
M+1 TCP connections in series
Response time = (M+1)O/R + (M+1)2RTT + sum of idle times
Persistent HTTP:
2 RTT to request and receive base HTML file
1 RTT to request and receive M images
Response time = (M+1)O/R + 3RTT + sum of idle times
Non-persistent HTTP with X parallel connections
Suppose M/X integer.
1 TCP connection for base file
M/X sets of parallel connections for images.
Response time = (M/X+1)O/R + (M/X + 1)2RTT + sum of idle
times
Introduction
1-326
HTTP Response time (in seconds)
RTT = 100 msec, O = 5 Kbytes, M=10 and X=5
20
18
16
14
12
10
8
6
4
2
0
non-persistent
persistent
parallel nonpersistent
28
100
1
10
Kbps Kbps Mbps Mbps
For low bandwidth, connection & response time dominated by
transmission time.
Persistent connections only give minor improvement over parallel
connections.
Introduction
1-327
HTTP Response time (in seconds)
RTT =1 sec, O = 5 Kbytes, M=10 and X=5
70
60
50
non-persistent
40
persistent
30
20
parallel nonpersistent
10
0
28
100
1
10
Kbps Kbps Mbps Mbps
For larger RTT, response time dominated by TCP establishment
& slow start delays. Persistent connections now give important
improvement: particularly in high delaybandwidth networks.
Introduction
1-328
Chapter 3: Summary
principles behind transport
layer services:
multiplexing,
demultiplexing
reliable data transfer
flow control
congestion control
instantiation and
implementation in the
Internet
UDP
TCP
Next:
leaving the network
“edge” (application,
transport layers)
into the network
“core”
Introduction
1-329
Homework problems
14 15 17 26 27
31 38
Introduction
1-330
Programming Assignments
Implementing a Reliable Transport Protocol
Simplied
• Using udp
Introduction
1-331
Ethereal Lab
Exploring TCP
Introduction
1-332
Home work2 solutions
Problem 1.
a) F
b) T
c) F
d) F
Problem 4.
Application layer protocols: DNS and HTTP
Transport layer protocols: UDP for DNS; TCP
for HTTP
Introduction
1-333
Home work2 solutions
Problem 9.
1)
= (900,000 bits)/(1,500,000 bits/sec) = .6 sec
traffic intensity =(1.5 requests/sec)(.6
msec/request) = .9
Delay=0.6/(1-0.9)+2s=8s
2)
average access delay =(.6 sec)/[1 – (.6)(.9)] = 1.2
seconds
average response time for cache misses: =1.2
sec + 2 sec = 3.2
(.4)(0 sec) + (.6)(3.2 sec) = 1.92 seconds.
Introduction
1-334
Home work2 solutions
Problem 6
time to get the IP address
• Rtt1+Rtt2…+Rttn
total response time
• 2Rtt0+Rtt1+Rtt2…+Rttn
Introduction
1-335
Chapter 4: Network Layer
Chapter goals:
understand principles behind network layer
services:
network layer service models
Forwarding(存储转发) versus routing function
how a router works
routing (path selection)
dealing with scale
advanced topics: IPv6, mobility
instantiation, implementation in the Internet
Introduction
1-336
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP(Internet Control
Message Protocol)
IPv6
4.5 Routing algorithms
Link state(链路状态)
Distance Vector(距离向量)
Hierarchical routing(层次
路由)
4.6 Routing in the
Internet
RIP(Routing Information
Protocol)
OSPF(Open Shortest Path
First)
BGP(Border Gateway
Protocol)
4.7 Broadcast and
multicast routing
Introduction
1-337
Network layer
transport segment from
sending to receiving host
on sending side
encapsulates segments
into datagrams
on rcving side, delivers
segments to transport
layer
network layer protocols
in every host, router
Router examines header
fields in all IP datagrams
passing through it
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Introduction
1-338
Two Key Network-Layer Functions
forwarding: move
packets from router’s
input to appropriate
router output
routing: determine
route taken by
packets from source
to dest.
analogy:
routing: process of
planning trip from
source to dest
forwarding: process
of getting through
single interchange
routing algorithms
Introduction
1-339
Interplay between routing and forwarding
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
Introduction
1-340
Connection setup
3rd important function in some network architectures:
ATM, frame relay(帧中继), X.25
before datagrams flow, two end hosts and intervening
routers establish virtual connection
routers get involved
network vs transport layer connection service:
network: between two hosts (may also involve
inervening routers in case of VCs)
transport: between two processes
Introduction
1-341
Network service model
Q: What service model for “channel” transporting
datagrams from sender to receiver?
Example services for
individual datagrams:
guaranteed delivery
guaranteed delivery
with less than 40 msec
delay
Example services for a
flow of datagrams:
in-order datagram
delivery
guaranteed minimum
bandwidth to flow
restrictions on
changes in interpacket spacing
Introduction
1-342
Network layer service models:
Network
Architecture
Internet
ATM
ATM
Service
Model
Guarantees ?
Bandwidth Loss Order Timing
best effort none
CBR
(constant
bit rate)
ABR
(Available
bit rate)
constant
Rate
no
no
yes yes
guaranteed yes yes
Minimum
no
yes
Congestion
feedback
no (inferred
via loss)
no
Congestion
Not
Congestion
Maintain indication
ed
provided
Introduction
1-343
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-344
Network layer connection and
connection-less service
datagram network provides network-layer
connectionless service
VC network provides network-layer
connection service
analogous to the transport-layer services,
but:
service: host-to-host
no choice: network provides one or the other
implementation: in network core
Introduction
1-345
Virtual circuits
“source-to-dest path behaves much like telephone
circuit”
performance-wise
network actions along source-to-dest path
call setup, teardown for each call before data can flow
each packet carries VC identifier (not destination host
address)
every router on source-dest path maintains “state” for
each passing connection
link, router resources (bandwidth, buffers) may be
allocated to VC (dedicated resources = predictable service)
Introduction
1-346
VC implementation
a VC consists of:
1.
2.
3.
path from source to destination
VC numbers, one number for each link along
path
entries in forwarding tables in routers along
path
packet belonging to VC carries VC number
(rather than dest address)
VC number can be changed on each link.
New VC number comes from forwarding table
Introduction
1-347
Forwarding table
VC number
22
12
1
Forwarding table in
northwest router:
Incoming interface
1
2
3
1
…
2
32
3
interface
number
Incoming VC #
12
63
7
97
…
Outgoing interface
3
1
2
3
…
Outgoing VC #
22
18
17
87
…
Routers maintain connection state information!
Introduction
1-348
Virtual circuits: signaling protocols
used to setup, maintain teardown VC
used in ATM, frame-relay, X.25
not used in today’s Internet
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
6. Receive data application
3. Accept call transport
2. incoming call network
data link
physical
Introduction
1-349
Datagram(分组交换) networks
no call setup at network layer
routers: no state about end-to-end connections
no network-level concept of “connection”
packets forwarded using destination host address
packets between same source-dest pair may take
different paths
application
transport
network
data link 1. Send data
physical
application
transport
2. Receive data network
data link
physical
Introduction
1-350
Forwarding table
Destination Address Range
4 billion
possible entries
Link Interface
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
0
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
1
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
2
otherwise
3
Introduction
1-351
Longest prefix matching
Prefix Match
11001000 00010111 00010
11001000 00010111 00011000
11001000 00010111 00011
otherwise
Link Interface
0
1
2
3
Examples
DA: 11001000 00010111 00010110 10100001
Which interface?
DA: 11001000 00010111 00011000 10101010
Which interface?
Net mask: 255.255.255.0
Introduction
1-352
Rotue table example
Command: Route Print
Network Destination
Netmask
Gateway
Interface Metric
0.0.0.0
0.0.0.0
192.168.1.2 192.168.1.48 20
127.0.0.0
255.0.0.0
127.0.0.1
127.0.0.1
1
192.168.1.0 255.255.255.0 192.168.1.48 192.168.1.48 20
192.168.1.48 255.255.255.255
127.0.0.1
127.0.0.1 20
192.168.1.255 255.255.255.255 192.168.1.48 192.168.1.48 20
202.114.192.0 255.255.240.0 192.168.1.254 192.168.1.48
1
224.0.0.0
240.0.0.0 192.168.1.48 192.168.1.48 20
255.255.255.255 255.255.255.255 192.168.1.48 192.168.1.48
1
Default Gateway:
192.168.1.2
Command: Route add , route delete
Q:How use cernet and telcom together?
With Nat
Introduction
1-353
Datagram or VC network: why?
Internet (datagram)
data exchange among
ATM (VC)
evolved from telephony
computers
human conversation:
“elastic” service, no strict
strict timing, reliability
timing req.
requirements
“smart” end systems
need for guaranteed
(computers)
service
can adapt, perform
“dumb” end systems
control, error recovery
telephones
simple inside network,
complexity inside
complexity at “edge”
network
many link types
different characteristics
uniform service difficult
Introduction
1-354
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-355
Router Architecture Overview
Two key router functions:
run routing algorithms/protocol (RIP, OSPF, BGP)
forwarding datagrams from incoming to outgoing link
Introduction
1-356
Input Port Functions
Physical layer:
bit-level reception
Data link layer:
e.g., Ethernet
see chapter 5
Decentralized switching:
given datagram dest., lookup output port
using forwarding table in input port
memory
goal: complete input port processing at
‘line speed’
queuing: if datagrams arrive faster than
forwarding rate into switch fabric
Introduction
1-357
Three types of switching fabrics
Introduction
1-358
Switching Via Memory
First generation routers:
traditional computers with switching under direct
control of CPU
packet copied to system’s memory
speed limited by memory bandwidth (2 bus
crossings per datagram)
Input
Port
Memory
Output
Port
System Bus
Introduction
1-359
Switching Via a Bus
datagram from input port memory
to output port memory via a shared
bus
bus contention: switching speed
limited by bus bandwidth
1 Gbps bus, Cisco 1900: sufficient
speed for access and enterprise
routers (not regional or backbone)
Introduction
1-360
Switching Via An Interconnection
Network
overcome bus bandwidth limitations
Banyan networks, other interconnection nets
initially developed to connect processors in
multiprocessor
Advanced design: fragmenting datagram into fixed
length cells, switch cells through the fabric.
Cisco 12000: switches Gbps through the
interconnection network
Introduction
1-361
Output Ports
Buffering required when datagrams arrive from
fabric faster than the transmission rate
Scheduling discipline chooses among queued
datagrams for transmission
Introduction
1-362
Output port queueing
buffering when arrival rate via switch exceeds
output line speed
queueing (delay) and loss due to output port
buffer overflow!
Introduction
1-363
Input Port Queuing
Fabric slower than input ports combined -> queueing
may occur at input queues
Head-of-the-Line (HOL) blocking: queued datagram
at front of queue prevents others in queue from
moving forward
queueing delay and loss due to input buffer overflow!
Introduction
1-364
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-365
The Internet Network layer
Host, router network layer functions:
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
forwarding
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
Introduction
1-366
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-367
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
how much overhead
with TCP?
20 bytes of TCP
20 bytes of IP
= 40 bytes + app
layer overhead
32 bits
type of
ver head.
len service
length
fragment
16-bit identifier flgs
offset
upper
time to
header
layer
live
checksum
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
Introduction
1-368
IP Fragmentation & Reassembly
network links have MTU
(max.transfer size) - largest
possible link-level frame.
different link types,
different MTUs
large IP datagram divided
(“fragmented”) within net
one datagram becomes
several datagrams
“reassembled” only at final
destination
IP header bits used to
identify, order related
fragments
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
Introduction
1-369
IP Fragmentation and Reassembly
Example
4000 byte
datagram
MTU = 1500 bytes
ADSL in 1492?
• PPPOE in later
1480 bytes in
data field
offset =
1480/8
length ID fragflag offset
=4000 =x
=0
=0
One large datagram becomes
several smaller datagrams
length ID fragflag offset
=1500 =x
=1
=0
length ID fragflag offset
=1500 =x
=1
=185
length ID fragflag offset
=1040 =x
=0
=370
Introduction
1-370
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-371
IP Addressing: introduction
IP address: 32-bit
identifier for host,
router interface
interface: connection
between host/router
and physical link
router’s typically have
multiple interfaces
host typically has one
interface
IP addresses
associated with each
interface
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
Introduction
1
1-372
Subnets
IP address:
subnet part (high
order bits)
host part (low order
bits)
What’s a subnet ?
device interfaces with
same subnet part of IP
address
can physically reach
each other without
intervening router
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
subnet
223.1.3.1
223.1.3.2
network consisting of 3 subnets
Introduction
1-373
Subnets
Recipe
To determine the
subnets, detach each
interface from its
host or router,
creating islands of
isolated networks.
Each isolated network
is called a subnet.
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
Subnet mask: /24
Introduction
1-374
Subnets
223.1.1.2
How many?
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
Introduction
1-375
IP addressing: CIDR
CIDR: Classless InterDomain Routing
subnet portion of address of arbitrary length
address format: a.b.c.d/x, where x is # bits in
subnet portion of address
subnet
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
Introduction
1-376
IP addresses: how to get one?
Q: How does host get IP address?
hard-coded by system admin in a file
Wintel: control-panel->network->configuration>tcp/ip->properties
UNIX: /etc/rc.config
DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server
“plug-and-play”
(more in next chapter)
Introduction
1-377
IP addresses: how to get one?
Q: How does network get subnet part of IP
addr?
A: gets allocated portion of its provider ISP’s
address space
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
Introduction
1-378
Hierarchical addressing: route aggregation
Hierarchical addressing allows efficient advertisement of routing
information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
“Send me anything
with addresses
beginning
199.31.0.0/16”
Introduction
1-379
Hierarchical addressing: more specific
routes
ISPs-R-Us has a more specific route to Organization 1
Organization 0
200.23.16.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
Organization 1
200.23.18.0/23
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
Introduction
1-380
IP addressing: the last word...
Q: How does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers
allocates addresses
manages DNS
assigns domain names, resolves disputes
Introduction
1-381
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.4
10.0.0.1
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
Introduction
1-382
NAT: Network Address Translation
Motivation: local network uses just one IP address as
far as outside world is concerned:
range of addresses not needed from ISP: just one IP
address for all devices
can change addresses of devices in local network
without notifying outside world
can change ISP without changing addresses of
devices in local network
devices inside local net not explicitly addressable,
visible by outside world (a security plus).
Introduction
1-383
NAT: Network Address Translation
Implementation: NAT router must:
outgoing datagrams: replace (source IP address, port
#) of every outgoing datagram to (NAT IP address,
new port #)
. . . remote clients/servers will respond using (NAT
IP address, new port #) as destination addr.
remember (in NAT translation table) every (source
IP address, port #) to (NAT IP address, new port #)
translation pair
incoming datagrams: replace (NAT IP address, new
port #) in dest fields of every incoming datagram
with corresponding (source IP address, port #)
stored in NAT table
Introduction
1-384
NAT: Network Address Translation
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
2
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40.186, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3: Reply arrives
dest. address:
138.76.29.7, 5001
3
1
10.0.0.1
10.0.0.4
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
10.0.0.2
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
Introduction
1-385
NAT: Network Address Translation
16-bit port-number field:
60,000 simultaneous connections with a single
LAN-side address!
NAT is controversial:
routers should only process up to layer 3
violates end-to-end argument
• NAT possibility must be taken into account by app
designers, eg, P2P applications
address shortage should instead be solved by
IPv6
Q:How use cernet and telcom together?
Introduction
1-386
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-387
ICMP: Internet Control Message Protocol
used by hosts & routers to
communicate network-level
information
error reporting:
unreachable host, network,
port, protocol
echo request/reply (used
by ping)
network-layer “above” IP:
ICMP msgs carried in IP
datagrams
ICMP message: type, code plus
first 8 bytes of IP datagram
causing error
Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
description
echo reply (ping)
dest. network unreachable
dest host unreachable
dest protocol unreachable
dest port unreachable
dest network unknown
dest host unknown
source quench (congestion
control - not used)
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
Introduction
1-388
Traceroute and ICMP
Source sends series of
UDP segments to dest
First has TTL =1
Second has TTL=2, etc.
Unlikely port number
When nth datagram arrives
to nth router:
Router discards datagram
And sends to source an
ICMP message (type 11,
code 0)
Message includes name of
router& IP address
When ICMP message
arrives, source calculates
RTT
Traceroute does this 3
times
Stopping criterion
UDP segment eventually
arrives at destination host
Destination returns ICMP
“host unreachable” packet
(type 3, code 3)
When source gets this
ICMP, stops.
Introduction
1-389
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-390
IPv6
Initial motivation: 32-bit address space soon
to be completely allocated.
Additional motivation:
header format helps speed processing/forwarding
header changes to facilitate QoS
IPv6 datagram format:
fixed-length 40 byte header
no fragmentation allowed
Introduction
1-391
IPv6 Header (Cont)
Priority: identify priority among datagrams in flow
Flow Label: identify datagrams in same “flow.”
(concept of“flow” not well defined).
Next header: identify upper layer protocol for data
Introduction
1-392
Other Changes from IPv4
Checksum: removed entirely to reduce
processing time at each hop
Options: allowed, but outside of header,
indicated by “Next Header” field
ICMPv6: new version of ICMP
additional message types, e.g. “Packet Too Big”
multicast group management functions
Introduction
1-393
Transition From IPv4 To IPv6
Not all routers can be upgraded simultaneous
no “flag days”
How will the network operate with mixed IPv4 and
IPv6 routers?
Tunneling: IPv6 carried as payload in IPv4
datagram among IPv4 routers
Introduction
1-394
Tunneling
Logical view:
Physical view:
E
F
IPv6
IPv6
IPv6
A
B
E
F
IPv6
IPv6
IPv6
IPv6
A
B
IPv6
tunnel
IPv4
IPv4
Introduction
1-395
Tunneling
Logical view:
Physical view:
A
B
IPv6
IPv6
A
B
C
IPv6
IPv6
IPv4
Flow: X
Src: A
Dest: F
data
A-to-B:
IPv6
E
F
IPv6
IPv6
D
E
F
IPv4
IPv6
IPv6
tunnel
Src:B
Dest: E
Src:B
Dest: E
Flow: X
Src: A
Dest: F
Flow: X
Src: A
Dest: F
data
data
B-to-C:
IPv6 inside
IPv4
B-to-C:
IPv6 inside
IPv4
Flow: X
Src: A
Dest: F
data
E-to-F:
IPv6
Introduction
1-396
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state(链路状态)
Distance Vector(距离向
量)
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-397
Interplay between routing, forwarding
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
Introduction
1-398
Graph abstraction
5
2
u
2
1
Graph: G = (N,E)
v
x
3
w
3
1
5
z
1
y
2
N = set of routers = { u, v, w, x, y, z }
E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Remark: Graph abstraction is useful in other network contexts
Example: P2P, where N is set of peers and E is set of TCP connections
Introduction
1-399
Graph abstraction: costs
5
2
u
v
2
1
x
• c(x,x’) = cost of link (x,x’)
3
w
3
1
5
z
1
y
- e.g., c(w,z) = 5
2
• cost could always be 1, or
inversely related to bandwidth,
or inversely related to
congestion
Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Question: What’s the least-cost path between u and z ?
Routing algorithm: algorithm that finds least-cost path
Introduction
1-400
Routing Algorithm classification
Global or decentralized
information?
Global:
all routers have complete
topology, link cost info
“link state” algorithms
Decentralized:
router knows physicallyconnected neighbors, link
costs to neighbors
iterative process of
computation, exchange of
info with neighbors
“distance vector” algorithms
Static or dynamic?
Static:
routes change slowly
over time
Dynamic:
routes change more
quickly
periodic update
in response to link
cost changes
Introduction
1-401
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-402
A Link-State Routing Algorithm
Dijkstra’s algorithm
net topology, link costs
known to all nodes
accomplished via “link
state broadcast”
all nodes have same info
computes least cost paths
from one node (‘source”) to
all other nodes
gives forwarding table
for that node
iterative: after k
iterations, know least cost
path to k dest.’s
Notation:
c(x,y): link cost from node
x to y; = ∞ if not direct
neighbors
D(v): current value of cost
of path from source to
dest. v
p(v): predecessor node
along path from source to v
N': set of nodes whose
least cost path definitively
known
Introduction
1-403
Dijsktra’s Algorithm
1 Initialization:
2 N' = {u}
3 for all nodes v
4
if v adjacent to u
5
then D(v) = c(u,v)
6
else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for all v adjacent to w and not in N' :
12
D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N'
Introduction
1-404
Dijkstra’s algorithm: example
Step
0
1
2
3
4
5
N'
u
ux
uxy
uxyv
uxyvw
uxyvwz
D(v),p(v) D(w),p(w)
2,u
5,u
2,u
4,x
2,u
3,y
3,y
D(x),p(x)
1,u
D(y),p(y)
∞
2,x
D(z),p(z)
∞
∞
4,y
4,y
4,y
5
2
u
v
2
1
x
3
w
3
1
5
z
1
y
2
Introduction
1-405
Dijkstra’s algorithm: example (2)
Resulting shortest-path tree from u:
v
w
u
z
x
y
Resulting forwarding table in u:
destination
link
v
x
(u,v)
(u,x)
y
(u,x)
w
(u,x)
z
(u,x)
Introduction
1-406
Dijkstra’s algorithm, discussion
Algorithm complexity: n nodes
each iteration: need to check all nodes, w, not in N
n(n+1)/2 comparisons: O(n2)
more efficient implementations possible: O(nlogn)
Oscillations possible:
e.g., link cost = amount of carried traffic
D
1
1
0
A
0 0
C
e
1+e
e
initially
B
1
2+e
A
0
D 1+e 1 B
0
0
C
… recompute
routing
0
D
1
A
0 0
C
2+e
B
1+e
… recompute
2+e
A
0
D 1+e 1 B
e
0
C
… recompute
Introduction
1-407
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state(链路状态)
Distance Vector(距离向
量)
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-408
Distance Vector Algorithm
Bellman-Ford Equation (dynamic programming)
Define
dx(y) := cost of least-cost path from x to y
Then
dx(y) = min
{c(x,v) + dv(y) }
v
where min is taken over all neighbors v of x
Introduction
1-409
Bellman-Ford example
5
2
u
v
2
1
x
3
w
3
1
5
z
1
y
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
2
B-F equation says:
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
Node that achieves minimum is next
hop in shortest path ➜ forwarding table
Introduction
1-410
Distance Vector Algorithm
Dx(y) = estimate of least cost from x to y
Node x knows cost to each neighbor v:
c(x,v)
Node x maintains distance vector Dx =
[Dx(y): y є N ]
Node x also maintains its neighbors’
distance vectors
For each neighbor v, x maintains
Dv = [Dv(y): y є N ]
Introduction
1-411
Distance vector algorithm (4)
Basic idea:
Each node periodically sends its own distance
vector estimate to neighbors
When a node x receives new DV estimate from
neighbor, it updates its own DV using B-F equation:
Dx(y) ← minv{c(x,v) + Dv(y)}
for each node y ∊ N
Under minor, natural conditions, the estimate
Dx(y) converge to the actual least cost dx(y)
Introduction
1-412
Distance Vector Algorithm (5)
Iterative, asynchronous:
each local iteration caused
by:
local link cost change
DV update message from
neighbor
Distributed:
each node notifies
neighbors only when its DV
changes
neighbors then notify
their neighbors if
necessary
Each node:
wait for (change in local link
cost or msg from neighbor)
recompute estimates
if DV to any dest has
changed, notify neighbors
Introduction
1-413
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 7 1 0
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
from
from
x
x ∞∞ ∞
y ∞∞ ∞
z 71 0
time
2
y
1
7
Introduction
z
1-414
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
x ∞∞ ∞
y ∞∞ ∞
z 71 0
from
from
from
from
x 0 2 7
y 2 0 1
z 7 1 0
cost to
x y z
x 0 2 7
y 2 0 1
z 3 1 0
x 0 2 3
y 2 0 1
z 3 1 0
cost to
x y z
x 0 2 3
y 2 0 1
z 3 1 0
x
2
y
1
7
z
cost to
x y z
from
from
from
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
x 0 2 3
y 2 0 1
z 7 1 0
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 3 1 0
time
Introduction
1-415
Distance Vector: link cost changes
Link cost changes:
node detects local link cost change
updates routing info, recalculates
distance vector
if DV changes, notify neighbors
“good
news
travels
fast”
1
x
4
y
50
1
z
At time t0, y detects the link-cost change, updates its DV,
and informs its neighbors.
At time t1, z receives the update from y and updates its table.
It computes a new least cost to x and sends its neighbors its DV.
At time t2, y receives z’s update and updates its distance table.
y’s least costs do not change and hence y does not send any
message to z.
Introduction
1-416
Distance Vector: link cost changes
Link cost changes:
good news travels fast
bad news travels slow -
“count to infinity” problem!
44 iterations before
algorithm stabilizes: see
text
60
x
4
y
50
1
z
Poisoned reverse:
If Z routes through Y to
get to X :
Z tells Y its (Z’s) distance
to X is infinite (so Y won’t
route to X via Z)
will this completely solve
count to infinity problem?
Introduction
1-417
Comparison of LS and DV algorithms
Message complexity
LS: with n nodes, E links,
O(nE) msgs sent
DV: exchange between
neighbors only
convergence time varies
Speed of Convergence
LS: O(n2) algorithm requires
O(nE) msgs
may have oscillations
DV: convergence time varies
may be routing loops
count-to-infinity problem
Robustness: what happens
if router malfunctions?
LS:
node can advertise
incorrect link cost
each node computes only
its own table
DV:
DV node can advertise
incorrect path cost
each node’s table used by
others
• error propagate thru
network
Introduction
1-418
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-419
Hierarchical Routing
Our routing study thus far - idealization
all routers identical
network “flat”
… not true in practice
scale: with 200 million
destinations:
can’t store all dest’s in
routing tables!
routing table exchange
would swamp links!
administrative autonomy
internet = network of
networks
each network admin may
want to control routing in its
own network
Introduction
1-420
Hierarchical Routing
aggregate routers into
regions, “autonomous
systems” (AS)
routers in same AS run
same routing protocol
Gateway router
Direct link to router in
another AS
“intra-AS” routing
protocol
routers in different AS
can run different intraAS routing protocol
Introduction
1-421
Interconnected ASes
3c
3a
3b
AS3
1a
2a
1c
1d
1b
Intra-AS
Routing
algorithm
2c
AS2
AS1
Inter-AS
Routing
algorithm
Forwarding
table
2b
Forwarding table is
configured by both
intra- and inter-AS
routing algorithm
Intra-AS sets entries
for internal dests
Inter-AS & Intra-As
sets entries for
external dests
Introduction
1-422
Inter-AS tasks
AS1 needs:
1. to learn which dests
are reachable through
AS2 and which
through AS3
2. to propagate this
reachability info to all
routers in AS1
Job of inter-AS routing!
Suppose router in AS1
receives datagram for
which dest is outside
of AS1
Router should forward
packet towards one of
the gateway routers,
but which one?
3c
3a
3b
AS3
1a
2a
1c
1d
1b
2c
AS2
2b
AS1
Introduction
1-423
Example: Setting forwarding table in router 1d
Suppose AS1 learns (via inter-AS protocol) that subnet
x is reachable via AS3 (gateway 1c) but not via AS2.
Inter-AS protocol propagates reachability info to all
internal routers.
Router 1d determines from intra-AS routing info that
its interface I is on the least cost path to 1c.
Puts in forwarding table entry (x,I).
3c
3a
3b
AS3
1a
2a
1c
1d
1b
2c
AS2
2b
AS1
Introduction
1-424
Example: Choosing among multiple ASes
Now suppose AS1 learns from the inter-AS protocol
that subnet x is reachable from AS3 and from AS2.
To configure forwarding table, router 1d must
determine towards which gateway it should forward
packets for dest x.
This is also the job on inter-AS routing protocol!
3c
3a
3b
AS3
1a
2a
1c
1d
1b
2c
AS2
2b
AS1
Introduction
1-425
Example: Choosing among multiple ASes
Now suppose AS1 learns from the inter-AS protocol
that subnet x is reachable from AS3 and from AS2.
To configure forwarding table, router 1d must
determine towards which gateway it should forward
packets for dest x.
This is also the job on inter-AS routing protocol!
Hot potato routing: send packet towards closest of
two routers.
Learn from inter-AS
protocol that subnet
x is reachable via
multiple gateways
Use routing info
from intra-AS
protocol to determine
costs of least-cost
paths to each
of the gateways
Hot potato routing:
Choose the gateway
that has the
smallest least cost
Determine from
forwarding table the
interface I that leads
to least-cost gateway.
Enter (x,I) in
forwarding table
Introduction
1-426
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-427
Intra-AS Routing
Also known as Interior Gateway Protocols (IGP)
Most common Intra-AS routing protocols:
RIP: Routing Information Protocol
OSPF: Open Shortest Path First
IGRP: Interior Gateway Routing Protocol (Cisco
proprietary)
Introduction
1-428
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-429
RIP ( Routing Information Protocol)
Distance vector algorithm
Included in BSD-UNIX Distribution in 1982
Distance metric: # of hops (max = 15 hops)
From router A to subsets:
u
v
A
z
C
B
D
w
x
y
destination hops
u
1
v
2
w
2
x
3
y
3
z
2
Introduction
1-430
RIP advertisements
Distance vectors: exchanged among
neighbors every 30 sec via Response
Message (also called advertisement)
Each advertisement: list of up to 25
destination nets within AS
Introduction
1-431
RIP: Example
z
w
A
x
D
B
y
C
Destination Network
w
y
z
x
….
Next Router
Num. of hops to dest.
….
....
A
B
B
--
2
2
7
1
Routing table in D
Introduction
1-432
RIP: Example
Dest
w
x
z
….
Next
C
…
w
hops
1
1
4
...
A
Advertisement
from A to D
z
x
Destination Network
w
y
z
x
….
D
B
C
y
Next Router
Num. of hops to dest.
….
....
A
B
B A
--
Routing table in D
2
2
7 5
1
Introduction
1-433
RIP: Link Failure and Recovery
If no advertisement heard after 180 sec -->
neighbor/link declared dead
routes via neighbor invalidated
new advertisements sent to neighbors
neighbors in turn send out new advertisements (if
tables changed)
link failure info quickly (?) propagates to entire net
poison reverse used to prevent ping-pong loops
(infinite distance = 16 hops)
Introduction
1-434
RIP Table processing
RIP routing tables managed by application-level
process called route-d (daemon)
advertisements sent in UDP packets, periodically
repeated
routed
routed
Transprt
(UDP)
network
(IP)
link
physical
Transprt
(UDP)
forwarding
table
forwarding
table
network
(IP)
link
physical
Introduction
1-435
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-436
OSPF (Open Shortest Path First)
“open”: publicly available
Uses Link State algorithm
LS packet dissemination
Topology map at each node
Route computation using Dijkstra’s algorithm
OSPF advertisement carries one entry per neighbor
router
Advertisements disseminated to entire AS (via
flooding(泛洪))
Carried in OSPF messages directly over IP (rather than TCP
or UDP
Introduction
1-437
OSPF “advanced” features (not in RIP)
Security: all OSPF messages authenticated (to
prevent malicious intrusion)
Multiple same-cost paths allowed (only one path in
RIP)
For each link, multiple cost metrics for different
TOS (e.g., satellite link cost set “low” for best effort;
high for real time)
Integrated uni- and multicast support:
Multicast OSPF (MOSPF) uses same topology data
base as OSPF
Hierarchical OSPF in large domains.
Introduction
1-438
Hierarchical OSPF
Introduction
1-439
Hierarchical OSPF
Two-level hierarchy: local area, backbone.
Link-state advertisements only in area
each nodes has detailed area topology; only know
direction (shortest path) to nets in other areas.
Area border routers: “summarize” distances to nets
in own area, advertise to other Area Border routers.
Backbone routers: run OSPF routing limited to
backbone.
Boundary routers: connect to other AS’s.
Introduction
1-440
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-441
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): the de
facto standard
BGP provides each AS a means to:
1.
2.
3.
Obtain subnet reachability information from
neighboring ASs.
Propagate reachability information to all ASinternal routers.
Determine “good” routes to subnets based on
reachability information and policy.
allows subnet to advertise its existence to
rest of Internet: “I am here”
Introduction
1-442
BGP basics
Pairs of routers (BGP peers) exchange routing info
over semi-permanent TCP connections: BGP sessions
BGP sessions need not correspond to physical links.
When AS2 advertises a prefix to AS1, AS2 is
promising it will forward any datagrams destined to
that prefix towards the prefix.
AS2 can aggregate prefixes in its advertisement
3c
3a
3b
AS3
1a
AS1
2a
1c
1d
1b
2c
AS2
2b
eBGP session
iBGP session
Introduction
1-443
Distributing reachability info
With eBGP session between 3a and 1c, AS3 sends prefix
reachability info to AS1.
1c can then use iBGP do distribute this new prefix reach info
to all routers in AS1
1b can then re-advertise new reachability info to AS2 over
1b-to-2a eBGP session
When router learns of new prefix, creates entry for prefix
in its forwarding table.
3c
3a
3b
AS3
1a
AS1
2a
1c
1d
1b
2c
AS2
2b
eBGP session
iBGP session
Introduction
1-444
Path attributes & BGP routes
When advertising a prefix, advert includes BGP
attributes.
prefix + attributes = “route”
Two important attributes:
AS-PATH: contains ASs through which prefix advertisement
has passed: AS 67 AS 17
NEXT-HOP: Indicates specific internal-AS router to nexthop AS. (There may be multiple links from current AS to
next-hop-AS.)
When gateway router receives route advertisement,
uses import policy to accept/decline.
Introduction
1-445
BGP route selection
Router may learn about more than 1 route
to some prefix. Router must select route.
Elimination rules:
1.
2.
3.
4.
Local preference value attribute: policy
decision
Shortest AS-PATH
Closest NEXT-HOP router: hot potato routing
Additional criteria
Introduction
1-446
BGP messages
BGP messages exchanged using TCP.
BGP messages:
OPEN: opens TCP connection to peer and
authenticates sender
UPDATE: advertises new path (or withdraws old)
KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
NOTIFICATION: reports errors in previous msg;
also used to close connection
Introduction
1-447
BGP routing policy
legend:
B
W
provider
network
X
A
customer
network:
C
Y
Figure 4.5-BGPnew: a simple BGP scenario
A,B,C are provider networks
X,W,Y are customer (of provider networks)
X is dual-homed: attached to two networks
X does not want to route from B via X to C
.. so X will not advertise to B a route to C
Introduction
1-448
BGP routing policy (2)
legend:
B
W
provider
network
X
A
customer
network:
C
Y
A advertises to B the path AW
Figure 4.5-BGPnew: a simple BGP scenario
B advertises to X the path BAW
Should B advertise to C the path BAW?
No way! B gets no “revenue” for routing CBAW since neither
W nor C are B’s customers
B wants to force C to route to w via A
B wants to route only to/from its customers!
Introduction
1-449
Why different Intra- and Inter-AS routing ?
Policy:
Inter-AS: admin wants control over how its traffic
routed, who routes through its net.
Intra-AS: single admin, so no policy decisions needed
Scale:
hierarchical routing saves table size, reduced update
traffic
Performance:
Intra-AS: can focus on performance
Inter-AS: policy may dominate over performance
Introduction
1-450
Chapter 4: Network Layer
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-451
Broadcast Routing
Deliver packets from source to all other nodes
Source duplication is inefficient:
duplicate
duplicate
creation/transmission
R1
R1
duplicate
R2
R2
R3
R4
source
duplication
R3
R4
in-network
duplication
Source duplication: how does source
determine recipient addresses?
Introduction
1-452
In-network duplication
Flooding: when node receives brdcst pckt,
sends copy to all neighbors
Problems: cycles & broadcast storm
Controlled flooding: node only brdcsts pkt
if it hasn’t brdcst same packet before
Node keeps track of pckt ids already brdcsted
Or reverse path forwarding (RPF): only forward
pckt if it arrived on shortest path between
node and source
Introduction
1-453
Reverse Path Forwarding Example
Router transmits the
packet to all of its
outgoing links only if
the packet arrived on
the link that is on its
own shortest path
back to the source
source
A
B
c
F
E
D
G
Packet will be forwarded
Packet not forwarded beyond receiving router
Introduction
1-454
Does Controlled Flooding Work?
Both sequence number controlled flooding
and RPF avoid broadcast storms.
Are there any transmissions of redundant
broadcast packets?
A
Nodes B, C, D, E and F receive either
one or two redundant packets.
Ideally, every node should receive
only one copy of the broadcast
packet.
B
c
F
E
D
G
Introduction
1-455
Spanning Tree
First construct a spanning tree
Nodes forward copies only along spanning
tree
A
B
c
F
A
E
B
c
D
F
G
(a) Broadcast initiated at A
E
D
G
(b) Broadcast initiated at D
Introduction
1-456
Spanning Tree: Creation
Center node
Each node sends unicast join message to center
node
Message forwarded until it arrives at a node already
belonging to spanning tree
A
A
3
B
c
4
E
F
1
2
B
c
D
F
5
E
D
G
G
(a) Stepwise construction
of spanning tree
(b) Constructed spanning
tree
Introduction
1-457
Multicast(多波) Routing
Delivering a packet sent from a source
node to a subset of the other nodes in the
network.
There are two problems:
How to identify the receivers of a multicast
packet?
How to address the packet sent to these
receivers?
Possible solution: each multicast packet will
carry the IP addresses of all of the multiple
recipients.
Do we have these problems at unicast or broadcast?
Introduction
1-458
Multicast Routing Solution
A multicast packet is addressed using address
indirection(间接地址).
The group of receivers get a single identifier.
A copy of the packet that is addressed to the
group using the single identifier is delivered to all
of the multicast receivers associated with that
group.
Class D represents a multicast address.
Every node in the multicast group has two IP
addresses: its unique address and the multicast
address. (application Layer)
Introduction
1-459
Internet Multicast Service Model
128.59.16.12
128.119.40.186
multicast
group
226.17.30.197
128.34.108.63
128.34.108.60
multicast group concept: use of indirection
hosts addresses IP datagram to multicast group
routers forward multicast datagrams to hosts that
have “joined” that multicast group
Introduction
1-460
Multicast groups
class D Internet addresses reserved for multicast:
host group semantics:
o anyone can “join” (receive) multicast group
o anyone can send to multicast group
o no network-layer identification to hosts of
members
needed: infrastructure to deliver mcast-addressed
datagrams to all hosts that have joined that multicast
group
Introduction
1-461
Joining a mcast group: two-step process
local: host informs local mcast router of desire to join
group: IGMP (Internet Group Management Protocol)
wide area: local router interacts with other routers to
receive mcast datagram flow
many protocols (e.g., DVMRP, MOSPF, PIM)
IGMP
IGMP
wide-area
multicast
routing
IGMP
Introduction
1-462
IGMP: Internet Group Management
Protocol
host: sends IGMP report when application joins
mcast group
IP_ADD_MEMBERSHIP socket option
host need not explicitly “unjoin” group when
leaving
router: sends IGMP query at regular intervals
host belonging to a mcast group must reply to
query
query
report
Introduction
1-463
IGMP
router: Host
Membership Query msg
broadcast on LAN to all
hosts
host: Host Membership
Report msg to indicate
group membership
randomized delay before
responding
implicit leave via no reply
to Query
group-specific Query
Leave Group msg
last host replying to Query
can send explicit Leave
Group msg
router performs groupspecific query to see if any
hosts left in group
Introduced in RFC 2236
IGMP v3: current version
Introduction
1-464
Multicast Routing: Problem Statement
Goal: find a tree (or trees) connecting
routers having local mcast group members
tree: not all paths between routers used
source-based: different tree from each sender to rcvrs
shared-tree: same tree used by all group members
Shared tree
Source-based trees
Approaches for building mcast trees
Approaches:
source-based tree: one tree per source
shortest path trees
reverse path forwarding
group-shared tree: group uses one tree
minimal spanning (Steiner)
center-based trees
…we first look at basic approaches, then specific
protocols adopting these approaches
Shortest Path Tree
mcast forwarding tree: tree of shortest
path routes from source to all receivers
Dijkstra’s algorithm
S: source
LEGEND
R1
1
2
R4
R2
3
R3
router with attached
group member
5
4
R6
router with no attached
group member
R5
6
R7
i
link used for forwarding,
i indicates order link
added by algorithm
Reverse Path Forwarding
rely on router’s knowledge of unicast
shortest path from it to sender
each router has simple forwarding behavior:
if (mcast datagram received on incoming link
on shortest path back to center)
then flood datagram onto all outgoing links
else ignore datagram
Reverse Path Forwarding: example
S: source
LEGEND
R1
R4
router with attached
group member
R2
R5
R3
R6
R7
router with no attached
group member
datagram will be
forwarded
datagram will not be
forwarded
• result is a source-specific reverse SPT
– may be a bad choice with asymmetric links
Reverse Path Forwarding: pruning
forwarding tree contains subtrees with no mcast
group members
no need to forward datagrams down subtree
“prune” msgs sent upstream by router with no
downstream group members
LEGEND
S: source
R1
router with attached
group member
R4
R2
P
R5
R3
R6
P
R7
P
router with no attached
group member
prune message
links with multicast
forwarding
Shared-Tree: Steiner Tree
Steiner Tree: minimum cost tree
connecting all routers with attached group
members
problem is NP-complete
excellent heuristics exists
not used in practice:
computational complexity
information about entire network needed
Center-based trees
single delivery tree shared by all
one router identified as “center” of tree
to join:
edge router sends unicast join-msg addressed
to center router
join-msg “processed” by intermediate routers
and forwarded towards center
join-msg either hits existing tree branch for
this center, or arrives at center
path taken by join-msg becomes new branch of
tree for this router
Center-based trees: an example
Suppose R6 chosen as center:
LEGEND
R1
3
R2
router with attached
group member
R4
2
R5
R3
1
R6
R7
1
router with no attached
group member
path order in which join
messages generated
Internet Multicasting Routing: DVMRP
DVMRP: distance vector multicast routing
protocol, RFC1075
flood and prune: reverse path forwarding,
source-based tree
RPF tree based on DVMRP’s own routing tables
constructed by communicating DVMRP routers
no assumptions about underlying unicast
initial datagram to mcast group flooded
everywhere via RPF
routers not wanting group: send upstream prune
msgs
DVMRP: continued…
soft state: DVMRP router periodically (1 min.)
“forgets” branches are pruned:
mcast data again flows down unpruned branch
downstream router: reprune or else continue to
receive data
routers can quickly regraft to tree
following IGMP join at leaf
odds and ends
commonly implemented in commercial routers
Mbone routing done using DVMRP
Tunneling
Q: How to connect “islands” of multicast
routers in a “sea” of unicast routers?
physical topology
logical topology
mcast datagram encapsulated inside “normal” (non-multicast-
addressed) datagram
normal IP datagram sent thru “tunnel” via regular IP unicast to
receiving mcast router
receiving mcast router unencapsulates to get mcast datagram
PIM: Protocol Independent Multicast
not dependent on any specific underlying unicast
routing algorithm (works with all)
two different multicast distribution scenarios :
Dense:
Sparse:
group members
# networks with group
densely packed, in
“close” proximity.
bandwidth more
plentiful
members small wrt #
interconnected networks
group members “widely
dispersed”
bandwidth not plentiful
Consequences of Sparse-Dense Dichotomy:
Dense
group membership by
Sparse:
no membership until
routers assumed until
routers explicitly join
routers explicitly prune receiver- driven
data-driven construction
construction of mcast
on mcast tree (e.g., RPF)
tree (e.g., center-based)
bandwidth and non bandwidth and non-groupgroup-router processing
router processing
profligate
conservative
PIM- Dense Mode
flood-and-prune RPF, similar to DVMRP but
underlying unicast protocol provides RPF info
for incoming datagram
less complicated (less efficient) downstream
flood than DVMRP reduces reliance on
underlying routing algorithm
has protocol mechanism for router to detect it
is a leaf-node router
PIM - Sparse Mode
center-based approach
router sends join msg
to rendezvous point
(RP)
router can switch to
source-specific tree
increased performance:
less concentration,
shorter paths
R4
join
intermediate routers
update state and
forward join
after joining via RP,
R1
R2
R3
join
R5
join
R6
all data multicast
from rendezvous
point
R7
rendezvous
point
PIM - Sparse Mode
sender(s):
unicast data to RP,
which distributes down
RP-rooted tree
RP can extend mcast
tree upstream to
source
RP can send stop msg
if no attached
receivers
“no one is listening!”
R1
R4
join
R2
R3
join
R5
join
R6
all data multicast
from rendezvous
point
R7
rendezvous
point
Chapter 4: summary
4. 1 Introduction
4.2 Virtual circuit and
datagram networks
4.3 What’s inside a
router
4.4 IP: Internet
Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4.5 Routing algorithms
Link state
Distance Vector
Hierarchical routing
4.6 Routing in the
Internet
RIP
OSPF
BGP
4.7 Broadcast and
multicast routing
Introduction
1-482
Assignment
Programming Assignment
Ethereal Lab
Question and problems
Introduction
1-483
Chapter 5: The Data Link Layer(数
据链层) AND LAN(局域网)
Our goals:
understand principles behind data link layer
services:
error detection, correction(纠错)
sharing a broadcast channel: multiple access(多路访问)
Point-to-Point Link
link layer addressing
reliable data transfer, flow control: done!
instantiation and implementation of various link
layer technologies
Introduction
1-484
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM and MPLS
Introduction
1-485
Link Layer: Introduction
Some terminology:
“link”
hosts and routers are nodes
communication channels that
connect adjacent nodes along
communication path are links
wired links
wireless links
layer-2 packet is a frame(帧),
encapsulates datagram
data-link layer has responsibility of
transferring datagram from one node
to adjacent node over a link
Introduction
1-486
Link layer: context
Datagram transferred by
different link protocols
over different links:
e.g., Ethernet on first link,
frame relay on
intermediate links, 802.11
on last link
Each link protocol
provides different
services
e.g., may or may not
provide rdt over link
transportation analogy
trip from Princeton to
Lausanne
limo: Princeton to JFK
plane: JFK to Geneva
train: Geneva to Lausanne
tourist = datagram
transport segment =
communication link
transportation mode =
link layer protocol
travel agent = routing
algorithm
Introduction
1-487
Link Layer Services
Framing, link access:
encapsulate datagram into frame, adding header, trailer
channel access if shared medium
“MAC”(Medium Access control) addresses used in frame
headers to identify source, dest
• different from IP address!
Reliable delivery between adjacent nodes
we learned how to do this already (chapter 3)!
seldom used on low bit error link (fiber, some twisted
pair)
wireless links: high error rates
• Q: why both link-level and end-end reliability?
Introduction
1-488
Link Layer Services (more)
Flow Control:
pacing between adjacent sending and receiving nodes
Error Detection:
errors caused by signal attenuation, noise.
receiver detects presence of errors:
• signals sender for retransmission or drops frame
Error Correction:
receiver identifies and corrects bit error(s) without
resorting to retransmission
Half-duplex and full-duplex
with half duplex, nodes at both ends of link can transmit,
but not at same time
Introduction
1-489
Adaptors Communicating
datagram
sending
node
frame
adapter
rcving
node
link layer protocol
frame
adapter
link layer implemented in receiving side
“adaptor” (aka NIC)
looks for errors, rdt, flow
control, etc
Ethernet card, PCMCI
extracts datagram, passes
card, 802.11 card
to rcving node
sending side:
adapter is semi encapsulates datagram in
autonomous
a frame
link & physical layers
adds error checking bits,
rdt, flow control, etc.
Introduction
1-490
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM
Introduction
1-491
Error Detection
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
• Error detection not 100% reliable!
• protocol may miss some errors, but rarely
• larger EDC field yields better detection and correction
Introduction
1-492
Parity Checking
Single Bit Parity:
Detect single bit errors
Two Dimensional Bit Parity:
Detect and correct single bit errors
0
0
Introduction
1-493
Internet checksum
Goal: detect “errors” (e.g., flipped bits) in transmitted
segment (note: used at transport layer only)
Sender:
treat segment contents
as sequence of 16-bit
integers
checksum: addition (1’s
complement sum) of
segment contents
sender puts checksum
value into UDP checksum
field
Receiver:
compute checksum of received
segment
check if computed checksum
equals checksum field value:
NO - error detected
YES - no error detected. But
maybe errors nonetheless?
More later ….
Introduction
1-494
Checksumming: Cyclic Redundancy Check
view data bits, D, as a binary number
choose r+1 bit pattern (generator), G
goal: choose r CRC bits, R, such that
<D,R> exactly divisible by G (modulo 2)
receiver knows G, divides <D,R> by G. If non-zero remainder:
error detected!
can detect all burst errors less than r+1 bits
widely used in practice (ATM, HDLC)
Introduction
1-495
CRC Example
Want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by
G, want remainder R
R = remainder[
D.2r
G
]
Introduction
1-496
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM
Introduction
1-497
Multiple Access Links and Protocols
Two types of “links”:
point-to-point
PPP for dial-up access
point-to-point link between Ethernet switch and host
broadcast (shared wire or medium)
Old-fashioned Ethernet
upstream HFC
802.11 wireless LAN
Introduction
1-498
Multiple Access protocols
single shared broadcast channel
two or more simultaneous transmissions by nodes:
interference
collision if node receives two or more signals at the same time
multiple access protocol
distributed algorithm that determines how nodes
share channel, i.e., determine when node can transmit
communication about channel sharing must use channel
itself!
no out-of-band channel for coordination
Introduction
1-499
Ideal Multiple Access Protocol
Broadcast channel of rate R bps
1. When one node wants to transmit, it can send at
rate R.
2. When M nodes want to transmit, each can send at
average rate R/M
3. Fully decentralized:
no special node to coordinate transmissions
no synchronization of clocks, slots
4. Simple
Introduction
1-500
MAC Protocols: a taxonomy
Three broad classes:
Channel Partitioning
divide channel into smaller “pieces” (time slots,
frequency, code)
allocate piece to node for exclusive use
Random Access
channel not divided, allow collisions
“recover” from collisions
“Taking turns”
Nodes take turns, but nodes with more to send can take
longer turns
Introduction
1-501
Channel Partitioning MAC protocols: TDMA
TDMA: time division multiple access
access to channel in "rounds"
each station gets fixed length slot (length = pkt
trans time) in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6
idle
Introduction
1-502
Channel Partitioning MAC protocols: FDMA
FDMA: frequency division multiple access
channel spectrum divided into frequency bands
each station assigned fixed frequency band
unused transmission time in frequency bands go idle
example: 6-station LAN, 1,3,4 have pkt, frequency
frequency bands
bands 2,5,6 idle
Introduction
1-503
Random Access Protocols
When node has packet to send
transmit at full channel data rate R.
no a priori coordination among nodes
two or more transmitting nodes ➜ “collision”,
random access MAC protocol specifies:
how to detect collisions
how to recover from collisions (e.g., via delayed
retransmissions)
Examples of random access MAC protocols:
slotted ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA
Introduction
1-504
Slotted ALOHA
Assumptions
all frames same size
time is divided into
equal size slots, time to
transmit 1 frame
nodes start to transmit
frames only at
beginning of slots
nodes are synchronized
if 2 or more nodes
transmit in slot, all
nodes detect collision
Operation
when node obtains fresh
frame, it transmits in next
slot
no collision, node can send
new frame in next slot
if collision, node
retransmits frame in each
subsequent slot with prob.
p until success
Introduction
1-505
Slotted ALOHA
Pros
single active node can
continuously transmit
at full rate of channel
highly decentralized:
only slots in nodes
need to be in sync
simple
Cons
collisions, wasting slots
idle slots
nodes may be able to
detect collision in less
than time to transmit
packet
clock synchronization
Introduction
1-506
Slotted Aloha efficiency
Efficiency is the long-run
fraction of successful slots
when there are many nodes,
each with many frames to send
Suppose N nodes with
many frames to send,
each transmits in slot
with probability p
prob that node 1 has
success in a slot
= p(1-p)N-1
prob that any node has
a success = Np(1-p)N-1
For max efficiency
with N nodes, find p*
that maximizes
Np(1-p)N-1
For many nodes, take
limit of Np*(1-p*)N-1
as N goes to infinity,
gives 1/e = .37
At best: channel
used for useful
transmissions 37%
of time!
Introduction
1-507
Pure (unslotted) ALOHA
unslotted Aloha: simpler, no synchronization
when frame first arrives
transmit immediately
collision probability increases:
frame sent at t0 collides with other frames sent in [t0-1,t0+1]
Introduction
1-508
Pure Aloha efficiency
P(success by given node) = P(node transmits) .
P(no other node transmits in [p0-1,p0] .
P(no other node transmits in [p0-1,p0]
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)
… choosing optimum p and then letting n -> infty ...
Even worse !
= 1/(2e) = .18
Introduction
1-509
CSMA (Carrier Sense Multiple Access)
CSMA: listen before transmit:
If channel sensed idle: transmit entire frame
If channel sensed busy, defer transmission
Human analogy: don’t interrupt others!
Introduction
1-510
CSMA collisions
spatial layout of nodes
collisions can still occur:
propagation delay means
two nodes may not hear
each other’s transmission
collision:
entire packet transmission
time wasted
note:
role of distance & propagation
delay in determining collision
probability
Introduction
1-511
CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA
collisions detected within short time
colliding transmissions aborted, reducing channel
wastage
collision detection:
easy in wired LANs: measure signal strengths,
compare transmitted, received signals
difficult in wireless LANs: receiver shut off while
transmitting
human analogy: the polite conversationalist
Introduction
1-512
CSMA/CD collision detection
Ethernet
Introduction
1-513
“Taking Turns” MAC protocols
channel partitioning MAC protocols:
share channel efficiently and fairly at high load
inefficient at low load: delay in channel access,
1/N bandwidth allocated even if only 1 active
node!
Random access MAC protocols
efficient at low load: single node can fully
utilize channel
high load: collision overhead
“taking turns” protocols
look for best of both worlds!
Introduction
1-514
“Taking Turns” MAC protocols
Token passing:
Polling:
control token passed from
master node
one node to next
“invites” slave nodes
sequentially.
to transmit in turn
token message
concerns:
concerns:
polling overhead
latency
single point of
failure (master)
token overhead
latency
single point of failure (token)
Introduction
1-515
Summary of MAC protocols
What do you do with a shared media?
Channel Partitioning, by time, frequency or code
• Time Division, Frequency Division
Random partitioning (dynamic),
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard
in others (wireless)
• CSMA/CD used in Ethernet
• CSMA/CA used in 802.11
Taking Turns
• polling from a central site, token passing
Introduction
1-516
LAN technologies
Data link layer so far:
services, error detection/correction, multiple
access
Next: LAN technologies
addressing
Ethernet
hubs, switches
PPP
Introduction
1-517
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM
Introduction
1-518
MAC Addresses and ARP
32-bit IP address:
network-layer address
used to get datagram to destination IP subnet
MAC (or LAN or physical or Ethernet)
address:
used to get frame from one interface to another
physically-connected interface (same network)
48 bit MAC address (for most LANs)
burned in the adapter ROM
Introduction
1-519
LAN Addresses and ARP
Each adapter on LAN has unique LAN address
1A-2F-BB-76-09-AD
71-65-F7-2B-08-53
LAN
(wired or
wireless)
Broadcast address =
FF-FF-FF-FF-FF-FF
= adapter
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
Introduction
1-520
LAN Address (more)
MAC address allocation administered by IEEE
manufacturer buys portion of MAC address space
(to assure uniqueness)
Analogy:
(a) MAC address: like Social Security Number
(b) IP address: like postal address
MAC flat address ➜ portability
can move LAN card from one LAN to another
IP hierarchical address NOT portable
depends on IP subnet to which node is attached
Introduction
1-521
ARP: Address Resolution Protocol
Question: how to determine
MAC address of B
knowing B’s IP address?
137.196.7.78
1A-2F-BB-76-09-AD
137.196.7.23
Each IP node (Host,
Router) on LAN has
ARP table
ARP Table: IP/MAC
address mappings for
some LAN nodes
137.196.7.14
LAN
71-65-F7-2B-08-53
137.196.7.88
< IP address; MAC address; TTL>
58-23-D7-FA-20-B0
TTL (Time To Live): time
after which address
mapping will be forgotten
(typically 20 min)
0C-C4-11-6F-E3-98
Introduction
1-522
ARP protocol: Same LAN (network)
A wants to send datagram
to B, and B’s MAC address
not in A’s ARP table.
A broadcasts ARP query
packet, containing B's IP
address
Dest MAC address =
FF-FF-FF-FF-FF-FF
all machines on LAN
receive ARP query
B receives ARP packet,
replies to A with its (B's)
MAC address
frame sent to A’s MAC
address (unicast)
A caches (saves) IP-to-
MAC address pair in its
ARP table until information
becomes old (times out)
soft state: information
that times out (goes
away) unless refreshed
ARP is “plug-and-play”:
nodes create their ARP
tables without
intervention from net
administrator
Introduction
1-523
ARP cheat
How to implement?
Raw packet
Netrobocop
Command :
Arp –a
Arp -s
Access control
Arp bind
PPP
Lan crash
Lookback link
Same Arp Addr
Broadcast storm
Spanning
Treeprotocol
vlan
Limit users number
PPP
802.3x?
Introduction
1-524
DHCP: Dynamic Host Configuration Protocol
Goal: allow host to dynamically obtain its IP address
from network server when it joins network
Can renew its lease on address in use
Allows reuse of addresses (only hold address while connected
an “on”
Support for mobile users who want to join network (more
shortly)
DHCP overview:
host broadcasts “DHCP discover” msg
DHCP server responds with “DHCP offer” msg
host requests IP address: “DHCP request” msg
DHCP server sends address: “DHCP ack” msg
Introduction
1-525
DHCP client-server scenario
A
B
223.1.2.1
DHCP
server
223.1.1.1
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
E
arriving DHCP
client needs
address in this
network
Introduction
1-526
DHCP client-server scenario
DHCP server: 223.1.2.5
DHCP discover
arriving
client
src : 0.0.0.0, 68
dest.: 255.255.255.255,67
yiaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 654
Lifetime: 3600 secs
DHCP request
time
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
Introduction
1-527
Routing to another LAN
walkthrough: send datagram from A to B via R
assume A know’s B IP address
A
R
B
Two ARP tables in router R, one for each IP
network (LAN)
Introduction
1-528
A creates datagram with source A, destination B
A uses ARP to get R’s MAC address for 111.111.111.110
A creates link-layer frame with R's MAC address as dest,
frame contains A-to-B IP datagram
A’s adapter sends frame
R’s adapter receives frame
R removes IP datagram from Ethernet frame, sees its
destined to B
R uses ARP to get B’s MAC address
R creates frame containing A-to-B IP datagram sends to B
A
R
B
Introduction
1-529
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM
Introduction
1-530
Ethernet
“dominant” wired LAN technology:
cheap $20 for 100Mbs!
first widely used LAN technology
Simpler, cheaper than token LANs and ATM
Kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet
sketch
Introduction
1-531
Star topology
Bus topology popular through mid 90s
Now star topology prevails
Connection choices: hub or switch (more later)
hub or
switch
Introduction
1-532
Ethernet Frame Structure
Sending adapter encapsulates IP datagram (or other
network layer protocol packet) in Ethernet frame
Preamble:
7 bytes with pattern 10101010 followed by one
byte with pattern 10101011
used to synchronize receiver, sender clock rates
Introduction
1-533
Ethernet Frame Structure
(more)
Addresses: 6 bytes
if adapter receives frame with matching destination
address, or with broadcast address (eg ARP packet), it
passes data in frame to net-layer protocol
otherwise, adapter discards frame
Type: indicates the higher layer protocol (mostly
IP but others may be supported such as Novell
IPX and AppleTalk)
CRC: checked at receiver, if error is detected, the
frame is simply dropped
Introduction
1-534
Unreliable, connectionless service
Connectionless: No handshaking between sending
and receiving adapter.
Unreliable: receiving adapter doesn’t send acks or
nacks to sending adapter
stream of datagrams passed to network layer can have
gaps
gaps will be filled if app is using TCP
otherwise, app will see the gaps
Introduction
1-535
Ethernet uses CSMA/CD
No slots
adapter doesn’t transmit
if it senses that some
other adapter is
transmitting, that is,
carrier sense
transmitting adapter
aborts when it senses
that another adapter is
transmitting, that is,
collision detection
Before attempting a
retransmission,
adapter waits a
random time, that is,
random access
Introduction
1-536
Ethernet CSMA/CD algorithm
1. Adaptor receives
4. If adapter detects
datagram from net layer &
another transmission while
creates frame
transmitting, aborts and
sends jam signal
2. If adapter senses channel
idle, it starts to transmit 5. After aborting, adapter
frame. If it senses
enters exponential
channel busy, waits until
backoff: after the mth
channel idle and then
collision, adapter chooses
transmits
a K at random from
{0,1,2,…,2m-1}. Adapter
3. If adapter transmits
waits K·512 bit times and
entire frame without
returns to Step 2
detecting another
transmission, the adapter
is done with frame !
Introduction 1-537
Ethernet’s CSMA/CD (more)
Jam Signal: make sure all
other transmitters are
aware of collision; 48 bits
Bit time: .1 microsec for 10
Mbps Ethernet ;
for K=1023, wait time is
about 50 msec
Exponential Backoff:
Goal: adapt retransmission
attempts to estimated
current load
heavy load: random wait
will be longer
first collision: choose K
from {0,1}; delay is K· 512
bit transmission times
after second collision:
choose K from {0,1,2,3}…
after ten collisions, choose
K from {0,1,2,3,4,…,1023}
Introduction
1-538
CSMA/CD efficiency
Tprop = max prop between 2 nodes in LAN
ttrans = time to transmit max-size frame
efficiency
1
1 5t prop / ttrans
Efficiency goes to 1 as tprop goes to 0
Goes to 1 as ttrans goes to infinity
Much better than ALOHA, but still decentralized,
simple, and cheap
Introduction
1-539
10BaseT and 100BaseT
10/100 Mbps rate; latter called “fast ethernet”
T stands for Twisted Pair
Nodes connect to a hub: “star topology”; 100 m
max distance between nodes and hub
twisted pair
hub
Introduction
1-540
Hubs
Hubs are essentially physical-layer repeaters:
bits coming from one link go out all other links
at the same rate
no frame buffering
no CSMA/CD at hub: adapters detect collisions
provides net management functionality
twisted pair
hub
Introduction
1-541
Manchester encoding
Used in 10BaseT
Each bit has a transition
Allows clocks in sending and receiving nodes to
synchronize to each other
no need for a centralized, global clock among nodes!
Hey, this is physical-layer stuff!
Introduction
1-542
Gbit Ethernet
uses standard Ethernet frame format
allows for point-to-point links and shared
broadcast channels
in shared mode, CSMA/CD is used; short distances
between nodes required for efficiency
uses hubs, called here “Buffered Distributors”
Full-Duplex at 1 Gbps for point-to-point links
10 Gbps now !
Introduction
1-543
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Interconnections:
Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM
Introduction
1-544
Interconnecting with hubs
Backbone hub interconnects LAN segments
Extends max distance between nodes
But individual segment collision domains become one
large collision domain
Can’t interconnect 10BaseT & 100BaseT
hub
hub
hub
hub
Introduction
1-545
Switch
Link layer device
stores and forwards Ethernet frames
examines frame header and selectively
forwards frame based on MAC dest address
when frame is to be forwarded on segment,
uses CSMA/CD to access segment
transparent
hosts are unaware of presence of switches
plug-and-play, self-learning
switches do not need to be configured
Introduction
1-546
Forwarding
switch
1
2
hub
3
hub
hub
• How do determine onto which LAN segment to
forward frame?
• Looks like a routing problem...
Introduction
1-547
Self learning
A switch has a switch table
entry in switch table:
(MAC Address, Interface, Time Stamp)
stale entries in table dropped (TTL can be 60 min)
switch learns which hosts can be reached through
which interfaces
when frame received, switch “learns” location of
sender: incoming LAN segment
records sender/location pair in switch table
Introduction
1-548
Filtering/Forwarding
When switch receives a frame:
index switch table using MAC dest address
if entry found for destination
then{
if dest on segment from which frame arrived
then drop the frame
else forward the frame on interface indicated
}
else flood
forward on all but the interface
on which the frame arrived
Introduction
1-549
Switch example
Suppose C sends frame to D
1
B
C
A
B
E
G
3
2
hub
hub
hub
A
address interface
switch
1
1
2
3
I
D
E
F
G
H
Switch receives frame from from C
notes in bridge table that C is on interface 1
because D is not in table, switch forwards frame into
interfaces 2 and 3
frame received by D
Introduction
1-550
Switch example
Suppose D replies back with frame to C.
address interface
switch
B
C
hub
hub
hub
A
I
D
E
F
G
A
B
E
G
C
1
1
2
3
1
H
Switch receives frame from from D
notes in bridge table that D is on interface 2
because C is in table, switch forwards frame only to
interface 1
frame received by C
Introduction
1-551
Switch: traffic isolation
switch installation breaks subnet into LAN
segments
switch filters packets:
same-LAN-segment frames not usually
forwarded onto other LAN segments
segments become separate collision domains
switch
collision
domain
hub
collision domain
hub
collision domain
hub
Introduction
1-552
Switches: dedicated access
Switch with many
interfaces
Hosts have direct
connection to switch
No collisions; full duplex
Switching: A-to-A’ and B-to-B’
simultaneously, no collisions
A
C’
B
switch
C
B’
A’
Introduction
1-553
More on Switches
cut-through switching: frame forwarded
from input to output port without first
collecting entire frame
slight reduction in latency
combinations of shared/dedicated,
10/100/1000 Mbps interfaces
Q:Can Ethereal run over Switches or
routers?
Introduction
1-554
Institutional network
to external
network
mail server
web server
router
switch
IP subnet
hub
hub
hub
Introduction
1-555
Switches vs. Routers
both store-and-forward devices
routers: network layer devices (examine network layer
headers)
switches are link layer devices
routers maintain routing tables, implement routing
algorithms
switches maintain switch tables, implement
filtering, learning algorithms
Introduction
1-556
Summary comparison
hubs
routers
switches
traffic
isolation
no
yes
yes
plug & play
yes
no
yes
optimal
routing
cut
through
no
yes
no
yes
no
yes
Q:BroadStrom?
Introduction
1-557
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM
Introduction
1-558
Point to Point Data Link Control
one sender, one receiver, one link: easier than
broadcast link:
no Media Access Control
no need for explicit MAC addressing
e.g., dialup link, ISDN line
popular point-to-point DLC protocols:
PPP (point-to-point protocol)
HDLC: High level data link control (Data link
used to be considered “high layer” in protocol
stack!
Introduction
1-559
PPP Design Requirements [RFC 1557]
packet framing: encapsulation of network-layer
datagram in data link frame
carry network layer data of any network layer
protocol (not just IP) at same time
ability to demultiplex upwards
bit transparency: must carry any bit pattern in the
data field
error detection (no correction)
connection liveness: detect, signal link failure to
network layer
network layer address negotiation: endpoint can
learn/configure each other’s network address
Introduction
1-560
PPP non-requirements
no error correction/recovery
no flow control
out of order delivery OK
no need to support multipoint links (e.g., polling)
Error recovery, flow control, data re-ordering
all relegated to higher layers!
Introduction
1-561
PPP Data Frame
Flag: delimiter (framing)
Address: does nothing (only one option)
Control: does nothing; in the future possible
multiple control fields
Protocol: upper layer protocol to which frame
delivered (eg, PPP-LCP, IP, IPCP, etc)
Introduction
1-562
PPP Data Frame
info: upper layer data being carried
check: cyclic redundancy check for error
detection
Introduction
1-563
Byte Stuffing
“data transparency” requirement: data field
must be allowed to include flag pattern <01111110>
Q: is received <01111110> data or flag?
Sender: adds (“stuffs”) extra < 01111110> byte
after each < 01111110> data byte
Receiver:
two 01111110 bytes in a row: discard first byte,
continue data reception
single 01111110: flag byte
Introduction
1-564
Byte Stuffing
flag byte
pattern
in data
to send
flag byte pattern plus
stuffed byte in
transmitted data
Introduction
1-565
PPP Data Control Protocol
Before exchanging networklayer data, data link peers
must
configure PPP link (max.
frame length,
authentication)
learn/configure network
layer information
for IP: carry IP Control
Protocol (IPCP) msgs
(protocol field: 8021) to
configure/learn IP
address
Introduction
1-566
Link Layer
5.1 Introduction and
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
5.6 Hubs and switches
5.7 PPP
5.8 Link Virtualization:
ATM and MPLS
Introduction
1-567
Virtualization of networks
Virtualization of resources: a powerful abstraction in
systems engineering:
computing examples: virtual memory, virtual
devices
Virtual machines: e.g., java
IBM VM os from 1960’s/70’s
layering of abstractions: don’t sweat the details of
the lower layer, only deal with lower layers
abstractly
Introduction
1-568
The Internet: virtualizing networks
1974: multiple unconnected
nets
ARPAnet
data-over-cable
networks
packet satellite network (Aloha)
packet radio network
ARPAnet
"A Protocol for Packet Network Intercommunication",
V. Cerf, R. Kahn, IEEE Transactions on Communications,
May, 1974, pp. 637-648.
… differing in:
addressing
conventions
packet formats
error recovery
routing
satellite net
Introduction
1-569
The Internet: virtualizing networks
Internetwork layer (IP):
addressing: internetwork
appears as a single, uniform
entity, despite underlying local
network heterogeneity
network of networks
Gateway:
“embed internetwork packets in
local packet format or extract
them”
route (at internetwork level) to
next gateway
gateway
ARPAnet
satellite net
Introduction
1-570
Cerf & Kahn’s Internetwork Architecture
What is virtualized?
two layers of addressing: internetwork and local
network
new layer (IP) makes everything homogeneous at
internetwork layer
underlying local network technology
cable
satellite
56K telephone modem
today: ATM, MPLS
… “invisible” at internetwork layer. Looks like a link
layer technology to IP!
Introduction
1-571
ATM and MPLS
ATM, MPLS separate networks in their own
right
different service models, addressing, routing
from Internet
viewed by Internet as logical link connecting
IP routers
just like dialup link is really part of separate
network (telephone network)
ATM, MPSL: of technical interest in their
own right
Introduction
1-572
Asynchronous Transfer Mode: ATM
1990’s/00 standard for high-speed (155Mbps to
622 Mbps and higher) Broadband Integrated
Service Digital Network architecture
Goal: integrated, end-end transport of carry voice,
video, data
meeting timing/QoS requirements of voice, video
(versus Internet best-effort model)
“next generation” telephony: technical roots in
telephone world
packet-switching (fixed length packets, called
“cells”) using virtual circuits
Introduction
1-573
ATM architecture
adaptation layer: only at edge of ATM network
data segmentation/reassembly
roughly analagous to Internet transport layer
ATM layer: “network” layer
cell switching, routing
physical layer
Introduction
1-574
ATM: network or link layer?
Vision: end-to-end
transport: “ATM from
desktop to desktop”
ATM is a network
technology
Reality: used to connect
IP backbone routers
“IP over ATM”
ATM as switched
link layer,
connecting IP
routers
IP
network
ATM
network
Introduction
1-575
ATM Adaptation Layer (AAL)
ATM Adaptation Layer (AAL): “adapts” upper
layers (IP or native ATM applications) to ATM
layer below
AAL present only in end systems, not in switches
AAL layer segment (header/trailer fields, data)
fragmented across multiple ATM cells
analogy: TCP segment in many IP packets
Introduction
1-576
ATM Adaptation Layer (AAL) [more]
Different versions of AAL layers, depending on ATM
service class:
AAL1: for CBR (Constant Bit Rate) services, e.g. circuit emulation
AAL2: for VBR (Variable Bit Rate) services, e.g., MPEG video
AAL5: for data (eg, IP datagrams)
User data
AAL PDU
ATM cell
Introduction
1-577
ATM Layer
Service: transport cells across ATM network
analogous to IP network layer
very different services than IP network layer
Network
Architecture
Internet
Service
Model
Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
constant
rate
guaranteed
rate
guaranteed
minimum
none
no
no
no
yes
yes
yes
yes
yes
yes
no
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
no
yes
no
no
Introduction
1-578
ATM Layer: Virtual Circuits
VC transport: cells carried on VC from source to dest
call setup, teardown for each call before data can flow
each packet carries VC identifier (not destination ID)
every switch on source-dest path maintain “state” for each
passing connection
link,switch resources (bandwidth, buffers) may be allocated to
VC: to get circuit-like perf.
Permanent VCs (PVCs)
long lasting connections
typically: “permanent” route between to IP routers
Switched VCs (SVC):
dynamically set up on per-call basis
Introduction
1-579
ATM VCs
Advantages of ATM VC approach:
QoS performance guarantee for connection
mapped to VC (bandwidth, delay, delay jitter)
Drawbacks of ATM VC approach:
Inefficient support of datagram traffic
one PVC between each source/dest pair) does
not scale (N*2 connections needed)
SVC introduces call setup latency, processing
overhead for short lived connections
Introduction
1-580
ATM Layer: ATM cell
5-byte ATM cell header
48-byte payload
Why?: small payload -> short cell-creation delay
for digitized voice
halfway between 32 and 64 (compromise!)
Cell header
Cell format
Introduction
1-581
ATM cell header
VCI: virtual channel ID
will change from link to link thru net
PT: Payload type (e.g. RM cell versus data cell)
CLP: Cell Loss Priority bit
CLP = 1 implies low priority cell, can be
discarded if congestion
HEC: Header Error Checksum
cyclic redundancy check
Introduction
1-582
ATM Physical Layer (more)
Two pieces (sublayers) of physical layer:
Transmission Convergence Sublayer (TCS): adapts
ATM layer above to PMD sublayer below
Physical Medium Dependent: depends on physical
medium being used
TCS Functions:
Header checksum generation: 8 bits CRC
Cell delineation
With “unstructured” PMD sublayer, transmission
of idle cells when no data cells to send
Introduction
1-583
ATM Physical Layer
Physical Medium Dependent (PMD) sublayer
SONET/SDH: transmission frame structure (like a
container carrying bits);
bit synchronization;
bandwidth partitions (TDM);
several speeds: OC3 = 155.52 Mbps; OC12 = 622.08
Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 Gbps
TI/T3: transmission frame structure (old
telephone hierarchy): 1.5 Mbps/ 45 Mbps
unstructured: just cells (busy/idle)
Introduction
1-584
IP-Over-ATM
Classic IP only
3 “networks” (e.g.,
LAN segments)
MAC (802.3) and IP
addresses
IP over ATM
replace “network”
(e.g., LAN segment)
with ATM network
ATM addresses, IP
addresses
ATM
network
Ethernet
LANs
Ethernet
LANs
Introduction
1-585
IP-Over-ATM
app
transport
IP
Eth
phy
IP
AAL
Eth
ATM
phy phy
ATM
phy
ATM
phy
app
transport
IP
AAL
ATM
phy
Introduction
1-586
Datagram Journey in IP-over-ATM Network
at Source Host:
IP layer maps between IP, ATM dest address (using ARP)
passes datagram to AAL5
AAL5 encapsulates data, segments cells, passes to ATM layer
ATM network: moves cell along VC to destination
at Destination Host:
AAL5 reassembles cells into original datagram
if CRC OK, datagram is passed to IP
Introduction
1-587
IP-Over-ATM
Issues:
IP datagrams into
ATM AAL5 PDUs
from IP addresses
to ATM addresses
just like IP
addresses to
802.3 MAC
addresses!
ATM
network
Ethernet
LANs
Introduction
1-588
Multiprotocol label switching (MPLS)
initial goal: speed up IP forwarding by using fixed
length label (instead of IP address) to do
forwarding
borrowing ideas from Virtual Circuit (VC) approach
but IP datagram still keeps IP address!
PPP or Ethernet
header
MPLS header
label
20
IP header
remainder of link-layer frame
Exp S TTL
3
1
5
Introduction
1-589
MPLS capable routers
a.k.a. label-switched router
forwards packets to outgoing interface based
only on label value (don’t inspect IP address)
MPLS forwarding table distinct from IP forwarding
tables
signaling protocol needed to set up forwarding
RSVP-TE
forwarding possible along paths that IP alone would
not allow (e.g., source-specific routing) !!
use MPLS for traffic engineering
must co-exist with IP-only routers
Introduction
1-590
MPLS forwarding tables
in
label
out
label dest
10
12
8
out
interface
A
D
A
0
0
1
in
label
out
label dest
out
interface
10
6
A
1
12
9
D
0
R6
0
0
D
1
1
R3
R4
R5
0
0
R2
in
label
8
out
label dest
6
A
out
interface
0
in
label
6
outR1
label dest
-
A
A
out
interface
0
Introduction
1-591
Chapter 5: Summary
principles behind data link layer services:
error detection, correction
sharing a broadcast channel: multiple access
link layer addressing
instantiation and implementation of various link
layer technologies
Ethernet
switched LANS
PPP
virtualized networks as a link layer: ATM, MPLS
Introduction
1-592
Chapter 6: Wireless and Mobile Networks
Background:
# wireless (mobile) phone subscribers now
exceeds # wired phone subscribers!
computer nets: laptops, palmtops, PDAs,
Internet-enabled phone promise anytime
untethered Internet access
two important (but different) challenges
communication over wireless link
handling mobile user who changes point of
attachment to network
Introduction
1-593
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links,
characteristics
CDMA
6.3 IEEE 802.11
wireless LANs (“wi-fi”)
6.4 Cellular Internet
Access
architecture
standards (e.g., GSM)
Mobility
6.5 Principles:
addressing and routing
to mobile users
6.6 Mobile IP
6.7 Handling mobility in
cellular networks
6.8 Mobility and higherlayer protocols
6.9 Summary
Introduction
1-594
Elements of a wireless network
network
infrastructure
wireless hosts
laptop, PDA, IP phone
run applications
may be stationary
(non-mobile) or mobile
wireless does not
always mean mobility
Introduction
1-595
Elements of a wireless network
network
infrastructure
base station
typically connected to
wired network
relay - responsible
for sending packets
between wired
network and wireless
host(s) in its “area”
e.g., cell towers
802.11 access
points
Introduction
1-596
Elements of a wireless network
network
infrastructure
wireless link
typically used to
connect mobile(s) to
base station
also used as backbone
link
multiple access
protocol coordinates
link access
various data rates,
transmission distance
Introduction
1-597
Characteristics of selected wireless link
standards
54 Mbps
5-11 Mbps
802.11{a,g}
802.11b
.11 p-to-p link
1 Mbps
802.15
3G
UMTS/WCDMA, CDMA2000
384 Kbps
2G
IS-95 CDMA, GSM
56 Kbps
Indoor
Outdoor
Mid range
outdoor
Long range
outdoor
10 – 30m
50 – 200m
200m – 4Km
5Km – 20Km
Introduction
1-598
Elements of a wireless network
network
infrastructure
infrastructure mode
base station connects
mobiles into wired
network
handoff: mobile
changes base station
providing connection
into wired network
Introduction
1-599
Elements of a wireless network
Ad hoc mode
no base stations
nodes can only
transmit to other
nodes within link
coverage
nodes organize
themselves into a
network: route among
themselves
Introduction
1-600
Wireless Link Characteristics
Differences from wired link ….
decreased signal strength: radio signal
attenuates as it propagates through matter
(path loss)
interference from other sources: standardized
wireless network frequencies (e.g., 2.4 GHz)
shared by other devices (e.g., phone); devices
(motors) interfere as well
multipath propagation: radio signal reflects off
objects ground, arriving ad destination at
slightly different times
…. make communication across (even a point to point)
wireless link much more “difficult”
Introduction
1-601
Wireless network characteristics
Multiple wireless senders and receivers create
additional problems (beyond multiple access):
C
A
B
A
B
Hidden terminal problem
C
C’s signal
strength
A’s signal
strength
space
B, A hear each other
Signal fading:
A, C can not hear each other
B, C hear each other
B, C hear each other
B, A hear each other
means A, C unaware of their
interference at B
A, C can not hear each other
interferring at B
Introduction
1-602
Code Division Multiple Access (CDMA)
used in several wireless broadcast channels
(cellular, satellite, etc) standards
unique “code” assigned to each user; i.e., code set
partitioning
all users share same frequency, but each user has
own “chipping” sequence (i.e., code) to encode data
encoded signal = (original data) X (chipping
sequence)
decoding: inner-product of encoded signal and
chipping sequence
allows multiple users to “coexist” and transmit
simultaneously with minimal interference (if codes
are “orthogonal”)
Introduction
1-603
CDMA Encode/Decode
sender
d0 = 1
data
bits
code
Zi,m= di.cm
-1 -1 -1
1
-1
1 1 1
-1 -1 -1
slot 1
-1
slot 1
channel
output
1
-1
1 1 1 1 1 1
1
d1 = -1
1 1 1
channel output Zi,m
-1 -1 -1
slot 0
1
-1 -1 -1
-1
slot 0
channel
output
M
Di = S Zi,m.cm
m=1
received
input
code
receiver
1 1 1 1 1 1
1
-1 -1 -1
-1
1 1 1
1
-1
-1 -1 -1
-1
1 1 1
-1 -1 -1
slot 1
M
1
1
-1
-1 -1 -1
slot 0
d0 = 1
d1 = -1
slot 1
channel
output
slot 0
channel
output
Introduction
1-604
CDMA: two-sender interference
Introduction
1-605
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links,
characteristics
CDMA
6.3 IEEE 802.11
wireless LANs (“wi-fi”)
6.4 Cellular Internet
Access
architecture
standards (e.g., GSM)
Mobility
6.5 Principles:
addressing and routing
to mobile users
6.6 Mobile IP
6.7 Handling mobility in
cellular networks
6.8 Mobility and higherlayer protocols
6.9 Summary
Introduction
1-606
IEEE 802.11 Wireless LAN
802.11b
2.4-5 GHz unlicensed
radio spectrum
up to 11 Mbps
direct sequence spread
spectrum (DSSS) in
physical layer
• all hosts use same
chipping code
widely deployed, using
base stations
802.11a
5-6 GHz range
up to 54 Mbps
802.11g
2.4-5 GHz range
up to 54 Mbps
All use CSMA/CA for
multiple access
All have base-station
and ad-hoc network
versions
Introduction
1-607
802.11 LAN architecture
wireless host communicates
Internet
AP
hub, switch
or router
BSS 1
AP
BSS 2
with base station
base station = access
point (AP)
Basic Service Set (BSS)
(aka “cell”) in infrastructure
mode contains:
wireless hosts
access point (AP): base
station
ad hoc mode: hosts only
Introduction
1-608
802.11: Channels, association
802.11b: 2.4GHz-2.485GHz spectrum divided into
11 channels at different frequencies
AP admin chooses frequency for AP
interference possible: channel can be same as
that chosen by neighboring AP!
host: must associate with an AP
scans channels, listening for beacon frames
containing AP’s name (SSID) and MAC address
selects AP to associate with
may perform authentication [Chapter 8]
will typically run DHCP to get IP address in AP’s
subnet
Introduction
1-609
IEEE 802.11: multiple access
avoid collisions: 2+ nodes transmitting at same time
802.11: CSMA - sense before transmitting
don’t collide with ongoing transmission by other node
802.11: no collision detection!
difficult to receive (sense collisions) when transmitting due
to weak received signals (fading)
can’t sense all collisions in any case: hidden terminal, fading
goal: avoid collisions: CSMA/C(ollision)A(voidance)
A
C
A
B
B
C
C’s signal
strength
A’s signal
strength
space
Introduction
1-610
IEEE 802.11 MAC Protocol: CSMA/CA
802.11 sender
1 if sense channel idle for DIFS then
transmit entire frame (no CD)
2 if sense channel busy then
start random backoff time
timer counts down while channel idle
transmit when timer expires
if no ACK, increase random backoff
interval, repeat 2
802.11 receiver
- if frame received OK
sender
receiver
DIFS
data
SIFS
ACK
return ACK after SIFS (ACK needed due
to hidden terminal problem)
Introduction
1-611
Avoiding collisions (more)
idea: allow sender to “reserve” channel rather than random
access of data frames: avoid collisions of long data frames
sender first transmits small request-to-send (RTS) packets
to BS using CSMA
RTSs may still collide with each other (but they’re short)
BS broadcasts clear-to-send CTS in response to RTS
RTS heard by all nodes
sender transmits data frame
other stations defer transmissions
Avoid data frame collisions completely
using small reservation packets!
Introduction
1-612
Collision Avoidance: RTS-CTS exchange
A
AP
B
reservation collision
DATA (A)
defer
time
Introduction
1-613
802.11 frame: addressing
2
2
6
6
6
frame
address address address
duration
control
1
2
3
Address 1: MAC address
of wireless host or AP
to receive this frame
2
6
seq address
4
control
0 - 2312
4
payload
CRC
Address 4: used only
in ad hoc mode
Address 3: MAC address
of router interface to
which AP is attached
Address 2: MAC address
of wireless host or AP
transmitting this frame
Introduction
1-614
802.11 frame: addressing
R1 router
H1
Internet
AP
R1 MAC addr AP MAC addr
dest. address
source address
802.3 frame
AP MAC addr H1 MAC addr R1 MAC addr
address 1
address 2
address 3
802.11 frame
Introduction
1-615
802.11 frame: more
frame seq #
(for reliable ARQ)
duration of reserved
transmission time (RTS/CTS)
2
2
6
6
6
frame
address address address
duration
control
1
2
3
2
Protocol
version
2
4
1
Type
Subtype
To
AP
6
2
1
seq address
4
control
1
From More
AP
frag
1
Retry
1
0 - 2312
4
payload
CRC
1
1
1
WEP
Rsvd
Introduction
1-616
Power More
mgt
data
frame type
(RTS, CTS, ACK, data)
802.11: mobility within same subnet
H1 remains in same IP
subnet: IP address
can remain same
switch: which AP is
associated with H1?
self-learning (Ch. 5):
switch will see frame
from H1 and
“remember” which
switch port can be
used to reach H1
router
hub or
switch
BBS 1
AP 1
AP 2
H1
BBS 2
Introduction
1-617
802.15: personal area network
less than 10 m diameter
replacement for cables
(mouse, keyboard,
headphones)
ad hoc: no infrastructure
master/slaves:
slaves request permission to
send (to master)
master grants requests
802.15: evolved from
Bluetooth specification
2.4-2.5 GHz radio band
up to 721 kbps
P
S
P
radius of
coverage
M
S
P
S
P
M Master device
S Slave device
P Parked device (inactive)
Introduction
1-618
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links,
characteristics
CDMA
6.3 IEEE 802.11
wireless LANs (“wi-fi”)
6.4 Cellular Internet
Access
architecture
standards (e.g., GSM)
Mobility
6.5 Principles:
addressing and routing
to mobile users
6.6 Mobile IP
6.7 Handling mobility in
cellular networks
6.8 Mobility and higherlayer protocols
6.9 Summary
Introduction
1-619
Components of cellular network architecture
MSC
cell
connects cells to wide area net
manages call setup (more later!)
handles mobility (more later!)
covers geographical
region
base station (BS)
analogous to 802.11 AP
mobile users attach
to network through BS
air-interface:
physical and link layer
protocol between
mobile and BS
Mobile
Switching
Center
Public telephone
network, and
Internet
Mobile
Switching
Center
wired network
Introduction
1-620
Cellular networks: the first hop
Two techniques for sharing
mobile-to-BS radio
spectrum
combined FDMA/TDMA:
divide spectrum in
frequency channels, divide
each channel into time
slots
frequency
bands
CDMA: code division
multiple access
time slots
Introduction
1-621
Cellular standards: brief survey
2G systems: voice channels
IS-136 TDMA: combined FDMA/TDMA (north
america)
GSM (global system for mobile communications):
combined FDMA/TDMA
most widely deployed
IS-95 CDMA: code division multiple access
GSM
Don’t drown in a bowl
of alphabet soup: use this
oor reference only
Introduction
1-622
Cellular standards: brief survey
2.5 G systems: voice and data channels
for those who can’t wait for 3G service: 2G extensions
general packet radio service (GPRS)
evolved from GSM
data sent on multiple channels (if available)
enhanced data rates for global evolution (EDGE)
also evolved from GSM, using enhanced modulation
Date rates up to 384K
CDMA-2000 (phase 1)
data rates up to 144K
evolved from IS-95
Introduction
1-623
Cellular standards: brief survey
3G systems: voice/data
Universal Mobile Telecommunications Service (UMTS)
GSM next step, but using CDMA
CDMA-2000
….. more (and more interesting) cellular topics due to
mobility (stay tuned for details)
Introduction
1-624
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links,
characteristics
CDMA
6.3 IEEE 802.11
wireless LANs (“wi-fi”)
6.4 Cellular Internet
Access
architecture
standards (e.g., GSM)
Mobility
6.5 Principles:
addressing and routing
to mobile users
6.6 Mobile IP
6.7 Handling mobility in
cellular networks
6.8 Mobility and higherlayer protocols
6.9 Summary
Introduction
1-625
What is mobility?
spectrum of mobility, from the network perspective:
no mobility
mobile wireless user, mobile user,
using same access
connecting/
point
disconnecting
from network
using DHCP.
high mobility
mobile user, passing
through multiple
access point while
maintaining ongoing
connections (like cell
phone)
Introduction
1-626
Mobility: Vocabulary
home network: permanent
“home” of mobile
(e.g., 128.119.40/24)
Permanent address:
address in home
network, can always be
used to reach mobile
e.g., 128.119.40.186
home agent: entity that will
perform mobility functions on
behalf of mobile, when mobile
is remote
wide area
network
correspondent
Introduction
1-627
Mobility: more vocabulary
Permanent address: remains
constant (e.g., 128.119.40.186)
visited network: network
in which mobile currently
resides (e.g., 79.129.13/24)
Care-of-address: address
in visited network.
(e.g., 79,129.13.2)
wide area
network
correspondent: wants
to communicate with
mobile
foreign agent: entity
in visited network
that performs
mobility functions on
behalf of mobile.
Introduction
1-628
How do you contact a mobile friend:
Consider friend frequently changing
addresses, how do you find her?
I wonder where
Alice moved to?
search all phone
books?
call her parents?
expect her to let you
know where he/she is?
Introduction
1-629
Mobility: approaches
Let routing handle it: routers advertise permanent
address of mobile-nodes-in-residence via usual
routing table exchange.
routing tables indicate where each mobile located
no changes to end-systems
Let end-systems handle it:
indirect routing: communication from
correspondent to mobile goes through home
agent, then forwarded to remote
direct routing: correspondent gets foreign
address of mobile, sends directly to mobile
Introduction
1-630
Mobility: approaches
Let routing handle it: routers advertise permanent
not
address of mobile-nodes-in-residence
via usual
scalable
routing table exchange.
to millions of
routing tables indicate
mobiles where each mobile located
no changes to end-systems
let end-systems handle it:
indirect routing: communication from
correspondent to mobile goes through home
agent, then forwarded to remote
direct routing: correspondent gets foreign
address of mobile, sends directly to mobile
Introduction
1-631
Mobility: registration
visited network
home network
2
1
wide area
network
foreign agent contacts home
agent home: “this mobile is
resident in my network”
mobile contacts
foreign agent on
entering visited
network
End result:
Foreign agent knows about mobile
Home agent knows location of mobile
Introduction
1-632
Mobility via Indirect Routing
foreign agent
receives packets,
forwards to mobile
home agent intercepts
packets, forwards to
foreign agent
home
network
visited
network
3
wide area
network
correspondent
addresses packets
using home address
of mobile
1
2
4
mobile replies
directly to
correspondent
Introduction
1-633
Indirect Routing: comments
Mobile uses two addresses:
permanent address: used by correspondent (hence
mobile location is transparent to correspondent)
care-of-address: used by home agent to forward
datagrams to mobile
foreign agent functions may be done by mobile itself
triangle routing: correspondent-home-networkmobile
inefficient when
correspondent, mobile
are in same network
Introduction
1-634
Indirect Routing: moving between networks
suppose mobile user moves to another
network
registers with new foreign agent
new foreign agent registers with home agent
home agent update care-of-address for mobile
packets continue to be forwarded to mobile (but
with new care-of-address)
mobility, changing foreign networks
transparent: on going connections can be
maintained!
Introduction
1-635
Mobility via Direct Routing
correspondent forwards
to foreign agent
foreign agent
receives packets,
forwards to mobile
home
network
4
wide area
network
2
correspondent
requests, receives
foreign address of
mobile
visited
network
1
3
4
mobile replies
directly to
correspondent
Introduction
1-636
Mobility via Direct Routing: comments
overcome triangle routing problem
non-transparent to correspondent:
correspondent must get care-of-address
from home agent
what if mobile changes visited network?
Introduction
1-637
Accommodating mobility with direct routing
anchor foreign agent: FA in first visited network
data always routed first to anchor FA
when mobile moves: new FA arranges to have data
forwarded from old FA (chaining)
foreign net visited
at session start
wide area
network
anchor
foreign
agent
1
2
4
5
correspondent
agent
correspondent
3
new foreign
agent
new
foreign
network
Introduction
1-638
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links,
characteristics
CDMA
6.3 IEEE 802.11
wireless LANs (“wi-fi”)
6.4 Cellular Internet
Access
architecture
standards (e.g., GSM)
Mobility
6.5 Principles:
addressing and routing
to mobile users
6.6 Mobile IP
6.7 Handling mobility in
cellular networks
6.8 Mobility and higherlayer protocols
6.9 Summary
Introduction
1-639
Mobile IP
RFC 3220
has many features we’ve seen:
home agents, foreign agents, foreign-agent
registration, care-of-addresses, encapsulation
(packet-within-a-packet)
three components to standard:
indirect routing of datagrams
agent discovery
registration with home agent
Introduction
1-640
Mobile IP: indirect routing
foreign-agent-to-mobile packet
packet sent by home agent to foreign
agent: a packet within a packet
dest: 79.129.13.2
dest: 128.119.40.186
dest: 128.119.40.186
Permanent address:
128.119.40.186
dest: 128.119.40.186
Care-of address:
79.129.13.2
packet sent by
correspondent
Introduction
1-641
Mobile IP: agent discovery
agent advertisement: foreign/home agents advertise
service by broadcasting ICMP messages (typefield = 9)
0
type = 9
24
checksum
=9
code = 0
=9
H,F bits: home
and/or foreign agent
R bit: registration
required
16
8
standard
ICMP fields
router address
type = 16
length
registration lifetime
sequence #
RBHFMGV
bits
reserved
0 or more care-ofaddresses
mobility agent
advertisement
extension
Introduction
1-642
Mobile IP: registration example
home agent
HA: 128.119.40.7
foreign agent
COA: 79.129.13.2
visited network: 79.129.13/24
ICMP agent adv.
COA: 79.129.13.2
….
registration req.
COA: 79.129.13.2
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 9999
identification: 714
encapsulation format
….
Mobile agent
MA: 128.119.40.186
registration req.
COA: 79.129.13.2
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 9999
identification:714
….
registration reply
time
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 4999
Identification: 714
encapsulation format
….
registration reply
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 4999
Identification: 714
….
Introduction
1-643
Components of cellular network architecture
recall:
correspondent
wired public
telephone
network
MSC
MSC
MSC
MSC
MSC
different cellular networks,
operated by different providers
Introduction
1-644
Handling mobility in cellular networks
home network: network of cellular provider you
subscribe to (e.g., Sprint PCS, Verizon)
home location register (HLR): database in home
network containing permanent cell phone #,
profile information (services, preferences,
billing), information about current location
(could be in another network)
visited network: network in which mobile currently
resides
visitor location register (VLR): database with
entry for each user currently in network
could be home network
Introduction
1-645
GSM: indirect routing to mobile
home
network
HLR
2
home MSC consults HLR,
gets roaming number of
mobile in visited network
correspondent
home
Mobile
Switching
Center
1
3
VLR
Mobile
Switching
Center
4
Public
switched
telephone
network
call routed
to home network
home MSC sets up 2nd leg of call
to MSC in visited network
mobile
user
visited
network
MSC in visited network completes
call through base station to mobile
Introduction
1-646
GSM: handoff with common MSC
Handoff goal: route call via
new base station (without
interruption)
reasons for handoff:
VLR Mobile
Switching
Center
old
routing
old BSS
new
routing
new BSS
stronger signal to/from new
BSS (continuing connectivity,
less battery drain)
load balance: free up channel
in current BSS
GSM doesn’t mandate why to
perform handoff (policy), only
how (mechanism)
handoff initiated by old BSS
Introduction
1-647
GSM: handoff with common MSC
VLR Mobile
Switching
Center 2
4
1
8
old BSS
5
7
3
6
new BSS
1. old BSS informs MSC of impending
handoff, provides list of 1+ new BSSs
2. MSC sets up path (allocates resources)
to new BSS
3. new BSS allocates radio channel for
use by mobile
4. new BSS signals MSC, old BSS: ready
5. old BSS tells mobile: perform handoff to
new BSS
6. mobile, new BSS signal to activate new
channel
7. mobile signals via new BSS to MSC:
handoff complete. MSC reroutes call
8 MSC-old-BSS resources released
Introduction
1-648
GSM: handoff between MSCs
anchor MSC: first MSC
visited during cal
home network
correspondent
Home
MSC
call remains routed
through anchor MSC
new MSCs add on to end
anchor MSC
PSTN
MSC
MSC
MSC
(a) before handoff
of MSC chain as mobile
moves to new MSC
IS-41 allows optional
path minimization step
to shorten multi-MSC
chain
Introduction
1-649
GSM: handoff between MSCs
anchor MSC: first MSC
visited during cal
home network
correspondent
Home
MSC
call remains routed
through anchor MSC
new MSCs add on to end
anchor MSC
PSTN
MSC
MSC
MSC
(b) after handoff
of MSC chain as mobile
moves to new MSC
IS-41 allows optional
path minimization step
to shorten multi-MSC
chain
Introduction
1-650
Mobility: GSM versus Mobile IP
GSM element
Comment on GSM element
Mobile IP element
Home system
Network to which the mobile user’s permanent
phone number belongs
Home network
Gateway Mobile
Switching Center, or
“home MSC”. Home
Location Register
(HLR)
Home MSC: point of contact to obtain routable
address of mobile user. HLR: database in
home system containing permanent phone
number, profile information, current location of
mobile user, subscription information
Home agent
Visited System
Network other than home system where
mobile user is currently residing
Visited network
Visited Mobile
services Switching
Center.
Visitor Location
Record (VLR)
Visited MSC: responsible for setting up calls
to/from mobile nodes in cells associated with
MSC. VLR: temporary database entry in
visited system, containing subscription
information for each visiting mobile user
Foreign agent
Mobile Station
Roaming Number
(MSRN), or “roaming
number”
Routable address for telephone call segment
between home MSC and visited MSC, visible
to neither the mobile nor the correspondent.
Care-ofaddress
Introduction
1-651
Wireless, mobility: impact on higher layer protocols
logically, impact should be minimal …
best effort service model remains unchanged
TCP and UDP can (and do) run over wireless, mobile
… but performance-wise:
packet loss/delay due to bit-errors (discarded
packets, delays for link-layer retransmissions), and
handoff
TCP interprets loss as congestion, will decrease
congestion window un-necessarily
delay impairments for real-time traffic
limited bandwidth of wireless links
Introduction
1-652
Chapter 6 Summary
Wireless
wireless links:
capacity, distance
channel impairments
CDMA
IEEE 802.11 (“wi-fi”)
CSMA/CA reflects
wireless channel
characteristics
cellular access
architecture
standards (e.g., GSM,
CDMA-2000, UMTS)
Mobility
principles: addressing,
routing to mobile users
home, visited networks
direct, indirect routing
care-of-addresses
case studies
mobile IP
mobility in GSM
impact on higher-layer
protocols
Introduction
1-653
Chapter 8: Network Security
Chapter goals:
understand principles of network security:
cryptography and its many uses beyond
“confidentiality”
authentication
message integrity
key distribution
security in practice:
firewalls
security in application, transport, network, link
layers
Introduction
1-654
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-655
What is network security?
Confidentiality: only sender, intended receiver
should “understand” message contents
sender encrypts message
receiver decrypts message
Authentication: sender, receiver want to confirm
identity of each other
Message Integrity: sender, receiver want to ensure
message not altered (in transit, or afterwards)
without detection
Access and Availability: services must be accessible
and available to users
Introduction
1-656
Friends and enemies: Alice, Bob, Trudy
well-known in network security world
Bob, Alice (lovers!) want to communicate “securely”
Trudy (intruder) may intercept, delete, add messages
Alice
data
channel
secure
sender
Bob
data, control
messages
secure
receiver
data
Trudy
Introduction
1-657
Who might Bob, Alice be?
… well, real-life Bobs and Alices!
Web browser/server for electronic
transactions (e.g., on-line purchases)
on-line banking client/server
DNS servers
routers exchanging routing table updates
other examples?
Introduction
1-658
There are bad guys (and girls) out there!
Q: What can a “bad guy” do?
A: a lot!
eavesdrop: intercept messages
actively insert messages into connection
impersonation: can fake (spoof) source address
in packet (or any field in packet)
hijacking: “take over” ongoing connection by
removing sender or receiver, inserting himself
in place
denial of service: prevent service from being
used by others (e.g., by overloading resources)
more on this later ……
Introduction
1-659
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-660
The language of cryptography
Alice’s
K encryption
A
key
plaintext
encryption
algorithm
ciphertext
Bob’s
K decryption
B key
decryption plaintext
algorithm
symmetric key crypto: sender, receiver keys identical
public-key crypto: encryption key public, decryption key
secret (private)
Introduction
1-661
Symmetric key cryptography
substitution cipher: substituting one thing for another
monoalphabetic cipher: substitute one letter for another
plaintext:
abcdefghijklmnopqrstuvwxyz
ciphertext:
mnbvcxzasdfghjklpoiuytrewq
E.g.:
Plaintext: bob. i love you. alice
ciphertext: nkn. s gktc wky. mgsbc
Q: How hard to break this simple cipher?:
brute force (how hard?)
other?
Introduction
1-662
Symmetric key cryptography
KA-B
KA-B
plaintext
message, m
encryption ciphertext
algorithm
K (m)
A-B
decryption plaintext
algorithm
m = K ( KA-B(m) )
A-B
symmetric key crypto: Bob and Alice share know same
(symmetric) key: K
A-B
e.g., key is knowing substitution pattern in mono
alphabetic substitution cipher
Q: how do Bob and Alice agree on key value?
Introduction
1-663
Symmetric key crypto: DES
DES: Data Encryption Standard
US encryption standard [NIST 1993]
56-bit symmetric key, 64-bit plaintext input
How secure is DES?
DES Challenge: 56-bit-key-encrypted phrase
(“Strong cryptography makes the world a safer
place”) decrypted (brute force) in 4 months
no known “backdoor” decryption approach
making DES more secure:
use three keys sequentially (3-DES) on each datum
use cipher-block chaining
Introduction
1-664
Symmetric key
crypto: DES
DES operation
initial permutation
16 identical “rounds” of
function application,
each using different
48 bits of key
final permutation
Introduction
1-665
AES: Advanced Encryption Standard
new (Nov. 2001) symmetric-key NIST
standard, replacing DES
processes data in 128 bit blocks
128, 192, or 256 bit keys
brute force decryption (try each key)
taking 1 sec on DES, takes 149 trillion
years for AES
Introduction
1-666
Public Key Cryptography
symmetric key crypto
requires sender,
receiver know shared
secret key
Q: how to agree on key
in first place
(particularly if never
“met”)?
public key cryptography
radically different
approach [DiffieHellman76, RSA78]
sender, receiver do
not share secret key
public encryption key
known to all
private decryption
key known only to
receiver
Introduction
1-667
Public key cryptography
+ Bob’s public
B key
K
K
plaintext
message, m
encryption ciphertext
algorithm
+
K (m)
B
- Bob’s private
B key
decryption plaintext
algorithm message
+
m = K B(K (m))
B
Introduction
1-668
Public key encryption algorithms
Requirements:
1
2
+
need K ( ) and K - ( ) such that
B
B
- +
K (K (m)) = m
B B
.
.
+
given public key KB , it should be
impossible to compute
private key KB
RSA: Rivest, Shamir, Adelson algorithm
Introduction
1-669
RSA: Choosing keys
1. Choose two large prime numbers p, q.
(e.g., 1024 bits each)
2. Compute n = pq, z = (p-1)(q-1)
3. Choose e (with e<n) that has no common factors
with z. (e, z are “relatively prime”).
4. Choose d such that ed-1 is exactly divisible by z.
(in other words: ed mod z = 1 ).
5. Public key is (n,e). Private key is (n,d).
+
KB
-
KB
Introduction
1-670
RSA: Encryption, decryption
0. Given (n,e) and (n,d) as computed above
1. To encrypt bit pattern, m, compute
e
e
c = m mod n (i.e., remainder when m is divided by n)
2. To decrypt received bit pattern, c, compute
d
m = c d mod n (i.e., remainder when c is divided by n)
Magic
d
m = (m e mod n) mod n
happens!
c
Introduction
1-671
RSA example:
Bob chooses p=5, q=7. Then n=35, z=24.
e=5 (so e, z relatively prime).
d=29 (so ed-1 exactly divisible by z.
encrypt:
decrypt:
letter
m
me
l
12
1524832
c
17
d
c
481968572106750915091411825223071697
c = me mod n
17
m = cd mod n letter
12
l
Introduction
1-672
RSA: Why is that
m = (m e mod n)
d
mod n
Useful number theory result: If p,q prime and
n = pq, then:
y
y mod (p-1)(q-1)
x mod n = x
mod n
e
(m mod n) d mod n = medmod n
= m
ed mod (p-1)(q-1)
mod n
(using number theory result above)
1
= m mod n
(since we chose ed to be divisible by
(p-1)(q-1) with remainder 1 )
= m
Introduction
1-673
RSA: another important property
The following property will be very useful later:
-
+
B
B
K (K (m))
+ = m = K (K (m))
B B
use public key
first, followed
by private key
use private key
first, followed
by public key
Result is the same!
Introduction
1-674
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-675
Authentication
Goal: Bob wants Alice to “prove” her identity
to him
Protocol ap1.0: Alice says “I am Alice”
“I am Alice”
Failure scenario??
Introduction
1-676
Authentication
Goal: Bob wants Alice to “prove” her identity
to him
Protocol ap1.0: Alice says “I am Alice”
“I am Alice”
in a network,
Bob can not “see”
Alice, so Trudy simply
declares
herself to be Alice
Introduction
1-677
Authentication: another try
Protocol ap2.0: Alice says “I am Alice” in an IP packet
containing her source IP address
Alice’s
IP address “I am Alice”
Failure scenario??
Introduction
1-678
Authentication: another try
Protocol ap2.0: Alice says “I am Alice” in an IP packet
containing her source IP address
Trudy can create
a packet
“spoofing”
Alice’s
Alice’s address
IP address “I am Alice”
Introduction
1-679
Authentication: another try
Protocol ap3.0: Alice says “I am Alice” and sends her
secret password to “prove” it.
Alice’s
Alice’s
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
Failure scenario??
Introduction
1-680
Authentication: another try
Protocol ap3.0: Alice says “I am Alice” and sends her
secret password to “prove” it.
Alice’s
Alice’s
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
playback attack: Trudy
records Alice’s packet
and later
plays it back to Bob
Alice’s
Alice’s
“I’m Alice”
IP addr password
Introduction
1-681
Authentication: yet another try
Protocol ap3.1: Alice says “I am Alice” and sends her
encrypted secret password to “prove” it.
Alice’s encrypted
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
Failure scenario??
Introduction
1-682
Authentication: another try
Protocol ap3.1: Alice says “I am Alice” and sends her
encrypted secret password to “prove” it.
Alice’s encrypted
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
record
and
playback
still works!
Alice’s encrypted
“I’m Alice”
IP addr password
Introduction
1-683
Authentication: yet another try
Goal: avoid playback attack
Nonce: number (R) used only once –in-a-lifetime
ap4.0: to prove Alice “live”, Bob sends Alice nonce, R. Alice
must return R, encrypted with shared secret key
“I am Alice”
R
KA-B(R)
Failures, drawbacks?
Alice is live, and
only Alice knows
key to encrypt
nonce, so it must
be Alice!
Introduction
1-684
Authentication: ap5.0
ap4.0 requires shared symmetric key
can we authenticate using public key techniques?
ap5.0: use nonce, public key cryptography
“I am Alice”
R
Bob computes
+ -
-
K A (R)
“send me your public key”
+
KA
KA(KA (R)) = R
and knows only Alice
could have the private
key, that encrypted R
such that
+ K (K (R)) = R
A A
Introduction
1-685
ap5.0: security hole
Man (woman) in the middle attack: Trudy poses as
Alice (to Bob) and as Bob (to Alice)
I am Alice
R
I am Alice
R
K (R)
T
K (R)
A
Send me your public key
+
K
T
Send me your public key
+
K
A
- +
m = K (K (m))
A A
+
K (m)
A
Trudy gets
- +
m = K (K (m))
T Alice
sends T
m to
+
K (m)
T
encrypted with
Alice’s public key
Introduction
1-686
ap5.0: security hole
Man (woman) in the middle attack: Trudy poses as
Alice (to Bob) and as Bob (to Alice)
Difficult to detect:
Bob receives everything that Alice sends, and vice
versa. (e.g., so Bob, Alice can meet one week later and
recall conversation)
problem is that Trudy receives all messages as well!
Introduction
1-687
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Message integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-688
Digital Signatures
Cryptographic technique analogous to handwritten signatures.
sender (Bob) digitally signs document,
establishing he is document owner/creator.
verifiable, nonforgeable: recipient (Alice) can
prove to someone that Bob, and no one else
(including Alice), must have signed document
Introduction
1-689
Digital Signatures
Simple digital signature for message m:
Bob signs m by encrypting with his private key
-
KB, creating “signed” message, KB(m)
Bob’s message, m
Dear Alice
Oh, how I have missed
you. I think of you all the
time! …(blah blah blah)
Bob
K B Bob’s private
key
Public key
encryption
algorithm
-
K B(m)
Bob’s message,
m, signed
(encrypted) with
his private key
Introduction
1-690
Digital Signatures (more)
-
Suppose Alice receives msg m, digital signature KB(m)
Alice verifies m signed by Bob by applying Bob’s
+
-
+
-
public key KB to KB(m) then checks KB(KB(m) ) = m.
+
-
If KB(KB(m) ) = m, whoever signed m must have used
Bob’s private key.
Alice thus verifies that:
Bob signed m.
No one else signed m.
Bob signed m and not m’.
Non-repudiation:
Alice can take m, and signature KB(m) to
court and prove that Bob signed m.
Introduction
1-691
Message Digests
Computationally expensive
to public-key-encrypt
long messages
Goal: fixed-length, easyto-compute digital
“fingerprint”
apply hash function H
to m, get fixed size
message digest, H(m).
large
message
m
H: Hash
Function
H(m)
Hash function properties:
many-to-1
produces fixed-size msg
digest (fingerprint)
given message digest x,
computationally
infeasible to find m such
that x = H(m)
Introduction
1-692
Internet checksum: poor crypto hash
function
Internet checksum has some properties of hash function:
produces fixed length digest (16-bit sum) of message
is many-to-one
But given message with given hash value, it is easy to find
another message with same hash value:
message
I O U 1
0 0 . 9
9 B O B
ASCII format
49 4F 55 31
30 30 2E 39
39 42 4F 42
B2 C1 D2 AC
message
I O U 9
0 0 . 1
9 B O B
ASCII format
49 4F 55 39
30 30 2E 31
39 42 4F 42
B2 C1 D2 AC
different messages
but identical checksums!
Introduction
1-693
Digital signature = signed message digest
Alice verifies signature and
integrity of digitally signed
message:
Bob sends digitally signed
message:
large
message
m
H: Hash
function
Bob’s
private
key
+
-
KB
encrypted
msg digest
H(m)
digital
signature
(encrypt)
encrypted
msg digest
KB(H(m))
large
message
m
H: Hash
function
KB(H(m))
Bob’s
public
key
+
KB
digital
signature
(decrypt)
H(m)
H(m)
equal
?
Introduction
1-694
Hash Function Algorithms
MD5 hash function widely used (RFC 1321)
computes 128-bit message digest in 4-step
process.
arbitrary 128-bit string x, appears difficult to
construct msg m whose MD5 hash is equal to x.
SHA-1 is also used.
US standard [NIST, FIPS PUB 180-1]
160-bit message digest
Introduction
1-695
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-696
Trusted Intermediaries
Symmetric key problem:
Public key problem:
How do two entities
When Alice obtains
establish shared secret
key over network?
Solution:
trusted key distribution
center (KDC) acting as
intermediary between
entities
Bob’s public key (from
web site, e-mail,
diskette), how does she
know it is Bob’s public
key, not Trudy’s?
Solution:
trusted certification
authority (CA)
Introduction
1-697
Key Distribution Center (KDC)
Alice, Bob need shared symmetric key.
KDC: server shares different secret key with each
registered user (many users)
Alice, Bob know own symmetric keys, KA-KDC KB-KDC , for
communicating with KDC.
KDC
KA-KDC KP-KDC
KP-KDC
KB-KDC
KA-KDC
KX-KDC
KY-KDC
KB-KDC
KZ-KDC
Introduction
1-698
Key Distribution Center (KDC)
Q: How does KDC allow Bob, Alice to determine shared
symmetric secret key to communicate with each other?
KDC
generates
R1
KA-KDC(A,B)
Alice
knows
R1
KA-KDC(R1, KB-KDC(A,R1) )
KB-KDC(A,R1)
Bob knows to
use R1 to
communicate
with Alice
Alice and Bob communicate: using R1 as
session key for shared symmetric encryption
Introduction
1-699
Certification Authorities
Certification authority (CA): binds public key to
particular entity, E.
E (person, router) registers its public key with CA.
E provides “proof of identity” to CA.
CA creates certificate binding E to its public key.
certificate containing E’s public key digitally signed by CA
– CA says “this is E’s public key”
Bob’s
public
key
Bob’s
identifying
information
+
KB
digital
signature
(encrypt)
CA
private
key
K-
CA
+
KB
certificate for
Bob’s public key,
signed by CA
Introduction
1-700
Certification Authorities
When Alice wants Bob’s public key:
gets Bob’s certificate (Bob or elsewhere).
apply CA’s public key to Bob’s certificate, get
Bob’s public key
+
KB
digital
signature
(decrypt)
CA
public
key
Bob’s
public
+
key
KB
+
K CA
Introduction
1-701
A certificate contains:
Serial number (unique to issuer)
info about certificate owner, including algorithm
and key value itself (not shown)
info about
certificate
issuer
valid dates
digital
signature by
issuer
Introduction
1-702
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-703
Firewalls
firewall
isolates organization’s internal net from larger
Internet, allowing some packets to pass,
blocking others.
public
Internet
administered
network
firewall
Introduction
1-704
Firewalls: Why
prevent denial of service attacks:
SYN flooding: attacker establishes many bogus
TCP connections, no resources left for “real”
connections.
prevent illegal modification/access of internal data.
e.g., attacker replaces CIA’s homepage with
something else
allow only authorized access to inside network (set of
authenticated users/hosts)
two types of firewalls:
application-level
packet-filtering
Introduction
1-705
Packet Filtering
Should arriving
packet be allowed
in? Departing packet
let out?
internal network connected to Internet via
router firewall
router filters packet-by-packet, decision to
forward/drop packet based on:
source IP address, destination IP address
TCP/UDP source and destination port numbers
ICMP message type
TCP SYN and ACK bits
Introduction
1-706
Packet Filtering
Example 1: block incoming and outgoing
datagrams with IP protocol field = 17 and with
either source or dest port = 23.
All incoming and outgoing UDP flows and telnet
connections are blocked.
Example 2: Block inbound TCP segments with
ACK=0.
Prevents external clients from making TCP
connections with internal clients, but allows
internal clients to connect to outside.
Introduction
1-707
Application gateways
Filters packets on
application data as well
as on IP/TCP/UDP fields.
Example: allow select
internal users to telnet
outside.
host-to-gateway
telnet session
application
gateway
gateway-to-remote
host telnet session
router and filter
1. Require all telnet users to telnet through gateway.
2. For authorized users, gateway sets up telnet connection to
dest host. Gateway relays data between 2 connections
3. Router filter blocks all telnet connections not originating
from gateway.
Introduction
1-708
Limitations of firewalls and gateways
IP spoofing: router
can’t know if data
“really” comes from
claimed source
if multiple app’s. need
special treatment, each
has own app. gateway.
client software must
know how to contact
gateway.
filters often use all or
nothing policy for UDP.
tradeoff: degree of
communication with
outside world, level of
security
many highly protected
sites still suffer from
attacks.
e.g., must set IP address
of proxy in Web
browser
Introduction
1-709
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
Introduction
1-710
Internet security threats
Mapping:
before attacking: “case the joint” – find out
what services are implemented on network
Use ping to determine what hosts have
addresses on network
Port-scanning: try to establish TCP connection
to each port in sequence (see what happens)
nmap (http://www.insecure.org/nmap/) mapper:
“network exploration and security auditing”
Countermeasures?
Introduction
1-711
Internet security threats
Mapping: countermeasures
record traffic entering network
look for suspicious activity (IP addresses, ports
being scanned sequentially)
Introduction
1-712
Internet security threats
Packet sniffing:
broadcast media
promiscuous NIC reads all packets passing by
can read all unencrypted data (e.g. passwords)
e.g.: C sniffs B’s packets
C
A
src:B dest:A
payload
B
Countermeasures?
Introduction
1-713
Internet security threats
Packet sniffing: countermeasures
all hosts in organization run software that
checks periodically if host interface in
promiscuous mode.
one host per segment of broadcast media
(switched Ethernet at hub)
C
A
src:B dest:A
payload
B
Introduction
1-714
Internet security threats
IP Spoofing:
can generate “raw” IP packets directly from
application, putting any value into IP source
address field
receiver can’t tell if source is spoofed
e.g.: C pretends to be B
C
A
src:B dest:A
Countermeasures?
payload
B
Introduction
1-715
Internet security threats
IP Spoofing: ingress filtering
routers should not forward outgoing packets
with invalid source addresses (e.g., datagram
source address not in router’s network)
great, but ingress filtering can not be mandated
for all networks
C
A
src:B dest:A
payload
B
Introduction
1-716
Internet security threats
Denial of service (DOS):
flood of maliciously generated packets “swamp”
receiver
Distributed DOS (DDOS): multiple coordinated
sources swamp receiver
e.g., C and remote host SYN-attack A
C
A
SYN
SYN
SYN
SYN
SYN
B
Countermeasures?
SYN
SYN
Introduction
1-717
Internet security threats
Denial of service (DOS): countermeasures
filter out flooded packets (e.g., SYN) before
reaching host: throw out good with bad
traceback to source of floods (most likely an
innocent, compromised machine)
C
A
SYN
SYN
SYN
SYN
SYN
B
SYN
SYN
Introduction
1-718
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Authentication
8.4 Integrity
8.5 Key Distribution and certification
8.6 Access control: firewalls
8.7 Attacks and counter measures
8.8 Security in many layers
8.8.1. Secure email
8.8.2. Secure sockets
8.8.3. IPsec
8.8.4. Security in 802.11
Introduction
1-719
Secure e-mail
Alice wants to send confidential e-mail, m, to Bob.
KS
m
K (.)
S
+
KS
+
.
K B( )
+
KS(m )
KS(m )
+
KB(KS )
.
KS( )
-
Internet
+
KB(KS )
KB
m
KS
-
.
K B( )
-
KB
Alice:
generates random symmetric private key, KS.
encrypts message with KS (for efficiency)
also encrypts KS with Bob’s public key.
sends both KS(m) and KB(KS) to Bob.
Introduction
1-720
Secure e-mail
Alice wants to send confidential e-mail, m, to Bob.
KS
m
K (.)
S
+
KS
+
.
K B( )
+
KS(m )
KS(m )
+
KB(KS )
.
KS( )
-
Internet
+
KB(KS )
KB
m
KS
-
.
K B( )
-
KB
Bob:
uses his private key to decrypt and recover KS
uses KS to decrypt KS(m) to recover m
Introduction
1-721
Secure e-mail (continued)
• Alice wants to provide sender authentication
message integrity.
+
-
KA
m
H(.)
-
.
KA( )
-
-
KA(H(m))
KA(H(m))
+
Internet
m
KA
+
.
KA( )
m
H(m )
compare
.
H( )
H(m )
• Alice digitally signs message.
• sends both message (in the clear) and digital signature.
Introduction
1-722
Secure e-mail (continued)
• Alice wants to provide secrecy, sender authentication,
message integrity.
-
KA
m
.
H( )
-
.
KA( )
-
KA(H(m))
+
KS
.
KS( )
+
m
KS
+
.
K B( )
+
Internet
+
KB(KS )
KB
Alice uses three keys: her private key, Bob’s public
key, newly created symmetric key
Introduction
1-723
Pretty good privacy (PGP)
Internet e-mail encryption
scheme, de-facto standard.
uses symmetric key
cryptography, public key
cryptography, hash
function, and digital
signature as described.
provides secrecy, sender
authentication, integrity.
inventor, Phil Zimmerman,
was target of 3-year
federal investigation.
A PGP signed message:
---BEGIN PGP SIGNED MESSAGE--Hash: SHA1
Bob:My husband is out of town
tonight.Passionately yours,
Alice
---BEGIN PGP SIGNATURE--Version: PGP 5.0
Charset: noconv
yhHJRHhGJGhgg/12EpJ+lo8gE4vB3mqJ
hFEvZP9t6n7G6m5Gw2
---END PGP SIGNATURE---
Introduction
1-724
Secure sockets layer (SSL)
transport layer
security to any TCPbased app using SSL
services.
used between Web
browsers, servers for
e-commerce (shttp).
security services:
server authentication
data encryption
client authentication
(optional)
server authentication:
SSL-enabled browser
includes public keys for
trusted CAs.
Browser requests
server certificate,
issued by trusted CA.
Browser uses CA’s
public key to extract
server’s public key from
certificate.
check your browser’s
security menu to see
its trusted CAs.
Introduction
1-725
SSL (continued)
Encrypted SSL session:
Browser generates
symmetric session key,
encrypts it with server’s
public key, sends
encrypted key to server.
Using private key, server
decrypts session key.
Browser, server know
session key
SSL: basis of IETF
Transport Layer
Security (TLS).
SSL can be used for
non-Web applications,
e.g., IMAP.
Client authentication
can be done with client
certificates.
All data sent into TCP
socket (by client or server)
encrypted with session key.
Introduction
1-726
IPsec: Network Layer Security
Network-layer secrecy:
sending host encrypts the
data in IP datagram
TCP and UDP segments;
ICMP and SNMP
messages.
Network-layer authentication
destination host can
authenticate source IP
address
Two principle protocols:
authentication header
(AH) protocol
encapsulation security
payload (ESP) protocol
For both AH and ESP, source,
destination handshake:
create network-layer
logical channel called a
security association (SA)
Each SA unidirectional.
Uniquely determined by:
security protocol (AH or
ESP)
source IP address
32-bit connection ID
Introduction
1-727
Authentication Header (AH) Protocol
provides source
authentication, data
integrity, no
confidentiality
AH header inserted
between IP header,
data field.
protocol field: 51
intermediate routers
process datagrams as
usual
IP header
AH header
AH header includes:
connection identifier
authentication data:
source- signed message
digest calculated over
original IP datagram.
next header field:
specifies type of data
(e.g., TCP, UDP, ICMP)
data (e.g., TCP, UDP segment)
Introduction
1-728
ESP Protocol
provides secrecy, host
authentication, data
integrity.
data, ESP trailer
encrypted.
next header field is in ESP
trailer.
ESP authentication
field is similar to AH
authentication field.
Protocol = 50.
authenticated
encrypted
IP header
ESP
ESP
ESP
TCP/UDP segment
header
trailer authent.
Introduction
1-729
IEEE 802.11 security
War-driving: drive around Bay area, see what 802.11
networks available?
More than 9000 accessible from public roadways
85% use no encryption/authentication
packet-sniffing and various attacks easy!
Securing 802.11
encryption, authentication
first attempt at 802.11 security: Wired Equivalent
Privacy (WEP): a failure
current attempt: 802.11i
Introduction
1-730
Wired Equivalent Privacy (WEP):
authentication as in protocol ap4.0
host requests authentication from access point
access point sends 128 bit nonce
host encrypts nonce using shared symmetric key
access point decrypts nonce, authenticates host
no key distribution mechanism
authentication: knowing the shared key is enough
Introduction
1-731
WEP data encryption
Host/AP share 40 bit symmetric key (semi
permanent)
Host appends 24-bit initialization vector (IV) to
create 64-bit key
64 bit key used to generate stream of keys, kiIV
kiIV used to encrypt ith byte, di, in frame:
ci = di XOR kiIV
IV and encrypted bytes, ci sent in frame
Introduction
1-732
802.11 WEP encryption
IV
(per frame)
KS: 40-bit
secret
symmetric
key
plaintext
frame data
plus CRC
key sequence generator
( for given KS, IV)
k1IV k2IV k3IV … kNIV kN+1IV… kN+1IV
d1
d2
d3 …
dN
CRC1 … CRC4
c1
c2
c3 …
cN
cN+1 … cN+4
802.11
IV
header
WEP-encrypted data
plus CRC
Figure 7.8-new1:
802.11encryption
WEP protocol
Sender-side
WEP
Introduction
1-733
Breaking 802.11 WEP encryption
Security hole:
24-bit IV, one IV per frame, -> IV’s eventually reused
IV transmitted in plaintext -> IV reuse detected
Attack:
Trudy causes Alice to encrypt known plaintext d1 d2
d3 d4 …
IV
Trudy sees: ci = di XOR ki
Trudy knows ci di, so can compute kiIV
IV
IV
IV
Trudy knows encrypting key sequence k1 k2 k3 …
Next time IV is used, Trudy can decrypt!
Introduction
1-734
802.11i: improved security
numerous (stronger) forms of encryption
possible
provides key distribution
uses authentication server separate from
access point
Introduction
1-735
802.11i: four phases of operation
STA:
client station
AP: access point
AS:
Authentication
server
wired
network
1 Discovery of
security capabilities
2 STA and AS mutually authenticate, together
generate Master Key (MK). AP servers as “pass through”
3 STA derives
Pairwise Master
Key (PMK)
4 STA, AP use PMK to derive
Temporal Key (TK) used for message
encryption, integrity
3 AS derives
same PMK,
sends to AP
Introduction
1-736
EAP: extensible authentication protocol
EAP: end-end client (mobile) to authentication
server protocol
EAP sent over separate “links”
mobile-to-AP (EAP over LAN)
AP to authentication server (RADIUS over UDP)
wired
network
EAP TLS
EAP
EAP over LAN (EAPoL)
IEEE 802.11
RADIUS
UDP/IP
Introduction
1-737
Network Security (summary)
Basic techniques…...
cryptography (symmetric and public)
authentication
message integrity
key distribution
…. used in many different security scenarios
secure email
secure transport (SSL)
IP sec
802.11
Introduction
1-738